我不问如何发现大多数数组中的元素，已经在此处详细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？
定义N = 2 n。该数组包含N元素。
定义M为maj出现在数组中的次数。 “多数元素”的定义是M > N/2。
现在把这个数组分成p[1] ... p[n]。将q0定义为包含零实例maj的对数。将q1定义为仅包含maj的一个实例的对数。将q2定义为包含maj的两个实例的对数。
然后N = 2 q0 + 2 q1 + 2 q2和M = q1 + 2 q2。
代入不等式限定大多数元件，并简化：
M > N/2
q1 + 2 q2 > (2 q0 + 2 q1 + 2 q2)/2
q1 + 2 q2 > q0 + q1 + q2
2 q2 > q0 + q2
q2 > q0
所以含有maj两个实例对数量超过含有maj零个实例对的数目。
现在定义M'为在运行算法后新数组中出现的次数maj。该算法为每个q1对删除一个maj，并且为每个q2对删除一个maj。所以M' = M - q1 - q2。
将N'定义为该算法产生的新阵列的大小。该算法删除每个q1对的两个元素，并为每个q2对删除两个元素。
但我们不知道算法为每个q0对删除了多少个元素。一些q0对包含两个不同的元素，并且算法删除这两个元素。但其他q0对包含相同（非maj）元素，并且该算法仅删除一个。
一个极端是所有的q0对都被完全删除。在这种情况下，算法删除2 q0元素，所以
N - 2 q1 - q2 - 2 q0 ≤ N'
另一个极端是，只有一个元件从每个q0对删除。在这种情况下，该算法删除q0元素，所以
N - 2 q1 - q2 - q0 ≥ N'
让我们回到“多数元件”的定义，并做一些代数：
M > N/2
M - q1 - q2 > N/2 - q1 - q2
M - q1 - q2 > (N - 2 q1 - 2 q2)/2
M - q1 - q2 > (N - 2 q1 - q2 - q2)/2
的左侧是M'。
M' > (N - 2 q1 - q2 - q2)/2
我们可以将右侧变成N'/2吗？首先，将两边乘以2：
2 M' > N - 2 q1 - q2 - q2
回想一下，我们证明了q2 > q0。因此
2 M' > N - 2 q1 - q2 - q2 > N - 2 q1 - q2 - q0
，并且由于我们推断N - 2 q1 - q2 - q0 ≥ N'，
2 M' > N - 2 q1 - q2 - q0 ≥ N'
所以
2 M' > N'
M' > N'/2
因此maj出现足够次新的阵列中是新的数组的大多数元素。 QED。
是的，有证据。
我们只对元素对a[i],a[i+1],i感兴趣。如果a[i]=a[i+1]，我们称这样一对“好”。其他双“坏”。与大多数候选人相同的元素是“常规”。一对很好的groovy元素是一对古怪的。
关于良好配对的一个简单事实是至少有一半的配对是常规的。假设情况并非如此;那么在好的对中，严格不到一半的元素是常规的，在不好的对中，不超过一半的元素是常规的。总的来说，严格不到一半的元素是常规的。这是一个矛盾。
所以我们已经确定至少有一半的好搭配是常规的。
现在消除所有不良对。仍然至少有一半的元素是常规的（因为只剩下好的配对，其中至少有一半是常规）。
现在消除良好配对中的所有其他元素。仍然至少有一半的元素是groovy（因为每个元素的数量简单地减半）。
这就是证明。
这是我的证明中的变体：
考虑4例对ARR [i]和改编第[i + 1]（或反之亦然，以便与一对并不重要）中，i为奇数。让少校是主要的元素，分钟任何轻微的元素：
一个， b，c，d全部> = 0。
案例1对主要元素的原始总和贡献2 | maj |并减少主要元素的最终总和| maj |' （算法执行后）除以1
第2种情况对| maj |和1 | min |是所有次要元素的原始和，并且| maj |'由1和| min |'由1
案例3贡献2 | | min |并减小| min |'由2
案例4贡献2 | | min |并减小| min |'通过1
因此，原始数组ARR []中的主要元素的总数量为：
|maj| = 2a + b
虽然所有次要元素的数量是：
|min| = b + 2c + 2d
由于|少将| > | min | ，
2a + b > b + 2c + 2d
2a > 2c + 2d
a > c + d
算法运行后，主要元素的新号码为：
|maj|' = |maj| - a - b
和微量元素的新号码是：
|min|' = |min| - b - 2c - d
代我们得到：
|maj|' = 2a + b - a - b = a
|min|' = b + 2c + 2d - b - 2c - d = d
Sinc Ë我们从是c + d <一个以上知道，和A，C，d都是> = 0，我们有
a > c + d =>
a > d =>
|maj|' > |min|'
因此少将仍然是新的数组中的主要元素。