我不问如何找到一个数组中的多数元素，它已经在长度讨论这里的查找数组中的元素大部分

I am not asking how to find the majority element in an array, which has been discussed at length here Find majority element in array

我的问题是如下：

有一个数组改编[1 ... 2N] ，这个数组的大部分元素是少校现在我将使用以下规则来删除元素改编，

There is an array arr[1...2n], the majority element of this array is maj, now I will use the following rule to delete elements in arr,

如果改编[I] ==改编[I + 1] ，删除改编[I] ，我= 1，3,5，...，2n个 - 1; 否则，如果改编[I]！=改编[I + 1] ，同时删除改编[I] 和改编[I + 1] ，i = 1，3，5，...，2N - 1

if arr[i] == arr[i + 1], delete arr[i], i = 1, 3, 5,..., 2n - 1; else if arr[i] != arr[i + 1], delete both arr[i] and arr[i + 1], i = 1, 3, 5, ..., 2n - 1.

那么我们可以得到一个新的数组 new_arr ，大部分元素的候选 new_arr 是 new_maj ， 没有任何证据证明 new_maj ==少校？

then we can get a new array new_arr, and candidate of the majority element for new_arr is new_maj, is there any proof to prove that new_maj == maj?

推荐答案

是有一个证明。

我们只关心元件对 A [1]，A [1 + 1] ，我奇。如果 A [1] = A [1 + 1] ，我们称这样一对好。其他对是坏。元素是等于大多数候选是常规。一双好时髦元素是一个常规对。

We are only interested in element pairs a[i],a[i+1], i odd. If a[i]=a[i+1], we call such a pair "good". Other pairs are "bad". Elements that are equal to the majority candidate are "groovy". A good pair of groovy elements is a groovy pair.

有关好事成双一个简单的事实是，至少有一半的好事成双是常规。假设它不是那么;那么当中好事成双，严格不到一半的元素是常规，坏对之间，不超过二分之一的元素是常规。总共，严格小于一半元素都是常规。这是一个矛盾。

The simple fact about good pairs is that at least one half of good pairs are groovy. Suppose it is not so; then among good pairs, strictly less than one half of elements are groovy, and among bad pairs, no more than one half of elements are groovy. In total, strictly less than one half of elements are groovy. This is a contradiction.

因此​​，我们已经建立了至少一个一半的良好对是常规

So we have established that at least one half of good pairs are groovy.

现在杜绝一切不良对。不过，至少有一半的所有元素都是常规（因为只有好事成双仍然存在，其中，至少有一半是常规）。

Now eliminate all bad pairs. Still at least one half of all elements are groovy (because only good pairs remain, and among those, at least one half are groovy).

现在消除好事成双所有其他元素。仍至少有一半的所有元素都是常规（因为每个元件的量被简单地减半）。

Now eliminate every other element from good pairs. Still at least one half of all elements are groovy (because amount of each element is simply halved).

这个结论的证明。