给定一组2n个元素,其中n是相似的,n是不同的

Question

给定2n个元素的数组,其中n个元素相同,其余n个元素都不同.编写一个C程序,找出数组中出现n次的值

我想通过以下方式 - 比较a [i]和[i + 1]并比较a [i]和a [i + 2]并返回元素

这将在O(n)时间运行..谁能提供更好的解决方案？

我正在经历一些解决方案,就像这样 -

1. 声明两个变量a)计数变量以跟踪多数元素的计数.
2. 多数元素.
3. 执行for循环并在步骤4-6之后重复,直到到达阵列结束.
4. 如果当前数组元素等于多数元素,则递增计数
5. 否则,如果count为0,则使用当前数组元素和递增计数更新多数元素.
6. 否则,如果count不为0,则递减计数.
7. 做另一个for循环并计算数组中多数元素的出现次数,如果它是数组大小的一半,那么我们找到了多数元素,否则就没有多数元素.

Answer 1

您可以使用多数元素算法作为具有O(1)空间的O(n)解的基础.

您需要一个存储元素的空间.选择第一个元素并存储它,如果下一个元素与存储的元素相同,则完成.如果没有,请从下一步重新启动算法.如果在此结束后没有找到元素,则表示元素按顺序排列,如(a,b),(a,c),(a,d)或(b,a),(a) ,c),(a,d),(e,a)..比较前四个元素,你发现了副本.

因为元素可以是任意顺序,所以你检查的前n/2个元素可能都是不同的.所以没有比O(n)更好的解决方案.