algorithm - 给定一个包含 2n 个元素的数组，其中 n 个相似，n 个不同

Question

给定一个包含 2n 个元素的数组，其中 n 个元素相同，其余 n 个元素都不同。写一个C程序找出数组中出现n次的值

我是这样想的——比较 a[i] 和 a[i+1] 和比较 a[i] 和 a[i+2]并返回元素

这将在 O(n) 时间内运行..任何人都可以提供更好的解决方案吗？

我正在经历一些这样说的解决方案-

1. Declare two variables a) count variable to keep track of count of majority element.
2. Majority element.
3. Do a for loop and repeat following steps 4-6 until end of array is reached.
4. if current array element equals majority element, increment count
5. else, if count is 0, update majority element with current array element and increment count.
6. else if count is not 0 then decrement count.
7. Do another for loop and count the number of occurrences of majority element in the array, if it's half the array size then we have found the majority element, else there's no majority element.

Answer 1

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

您需要空间来存储一个元素。选择第一个元素并存储它，如果下一个元素与存储的相同，则完成。如果不是，则从下一步重新启动算法。如果在这之后没有找到元素，则意味着该元素是成对排序的，例如 (a,b),(a,c),(a,d) 或 (b,a),(a ,c),(a,d),(e,a)..比较前四个元素，你发现了重复项。

由于元素可以按任意顺序排列，因此无论您检查的前 n/2 个元素是什么，它们都可能是不同的。所以没有比 O(n) 更好的解决方案。