arrays - 候选人在数组中寻找多数元素

Question

我不是在问如何找到数组中的多数元素，这里已经详细讨论了Find majority element in array

我的问题如下:

有一个数组arr[1...2n]，这个数组的多数元素是maj，现在我将使用下面的规则删除其中的元素arr,

如果 arr[i] == arr[i + 1]，删除 arr[i]，i = 1, 3, 5,..., 2n - 1;否则如果 arr[i] != arr[i + 1]，删除 arr[i] 和 arr[i + 1]， i = 1, 3, 5, ..., 2n - 1。

然后我们可以得到一个新数组new_arr，new_arr的众数候选是new_maj，有什么证据可以证明 new_maj == maj 吗？

Answer 1

是的，有证据。

我们只对元素对 a[i],a[i+1], i 奇数感兴趣。如果 a[i]=a[i+1]，我们称这样的一对“好”。其他对是“坏的”。等于多数候选者的元素是“groovy”。一对好的 groovy 元素是 groovy 对。

关于好对的一个简单事实是，至少有一半的好对是绝妙的。假设不是这样；那么在好的对中，严格少于一半的元素是 groovy，而在坏的对中，不超过二分之一的元素是 groovy。总的来说，只有不到一半的元素是 groovy。这是一个矛盾。

因此我们确定至少有一半的好配对是 groovy。

现在消除所有坏对。所有元素中至少有一半是 groovy(因为只剩下好的对，而在这些元素中，至少有一半是 groovy)。

现在从好的对中消除所有其他元素。仍然至少有一半的元素是 groovy(因为每个元素的数量只是减半)。

证明到此结束。