algorithm - 计算数组中的多数元素

Question

上周我接受了采访。我被问到以下问题:

Given an array of 2n elements, and out of this n elements are same, and the remaining are all different. Find the element that repeats n times.

There is no restriction on the range of the elements.

谁能给我一个有效的算法来解决这个问题？

Answer 1

“给定 2n 个元素的数组，这 n 个元素相同，其余元素不同。找到重复 n 次的元素。”

这可以使用以下算法在 O(n) 中完成:

1) 遍历数组，检查是否有任何元素 [i] 和 [i+1] 相同。

2) 遍历数组，检查是否有任何元素 [i] 和 [i+2] 相同。

3) 如果 n = 2(因此长度 = 4)，检查 0 和 3 是否相同。

解释:

称匹配元素为m，非匹配元素为r。

对于 n = 2，我们可以构造 mmrr、mrmr 和 mrrm - 因此我们必须检查间隙大小 0、1 以及唯一可以有间隙大小 2 的地方。

对于 n > 2，我们不能构建没有大小为 0 或 1 的间隙的数组。例如对于 n = 3，您必须这样开始:mrrmr...但是您必须放置一个 m。类似地，对于 n = 4，mrrmrrmm - 没有大小为 0 或 1 的间隙将要求随着 n 的增加，ms 的数量越来越多于 rs。证明这一点很容易。