我不是在问如何在数组中找到多数元素，这在这里已经详细讨论过了
我的问题如下:
有一个数组arr[1...2n]，该数组的多数元素是maj，现在我将使用以下规则删除arr中的元素，
if arr[i] == arr[i + 1], delete arr[i], i = 1,3,5，…， 2n - 1;else if arr[i] != arr[i + 1], delete arr[i]和arr[i + 1], i = 1,3,5，…， 1.
则可以得到一个新的数组new_arr, new_arr的多数元素候选是new_maj，有证据证明new_maj == maj吗?
是的，有证据。
我们只对元素对a[i],a[i+1], i奇数感兴趣。如果a[i]=a[i+1]，我们称这样的一对为"好"。其他配对是"坏的"。与多数候选元素相等的元素是"groovy"。一个好的groovy元素对就是一个groovy对。
因此我们已经确定至少有一半的好对是groovy。
现在消除所有坏对。所有元素中至少有一半是groovy(因为只剩下好的元素对，而其中至少有一半是groovy)。
现在消除好对中的所有其他元素。然而，至少有一半的元素是groovy(因为每个元素的数量只是减半)。
这就是证明的结论。
定义N = 2 n。数组包含N元素。
定义M为maj在数组中出现的次数。"多数元素"的定义是M > N/2 .
现在将数组分成对p[1] ... p[n]。定义q0为包含0个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实例的对的数量超过包含0个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 . 这是我的证明版本:
考虑对arr[i]和arr[i+1]的4种情况(反之亦然，对的顺序不重要)，i是奇数。设maj为主元素，min为任意小元素:
- maj maj -让这样的对的数量为a
- maj min -设这些对的个数为b
- min1 min2 -让这样的对的个数为c， min1 != min2
- min1 min1 -让这样的对的数量为d
a, b, c, d均>= 0
情形1为主元素的原始和|maj|贡献2，并将主元素的最终和|maj|'(在算法执行后)减少1
情形2将1加到所有次要元素的原始和|maj|， 1加到|min|，并将|maj|'减1，|min|'减1
Case 3对|min|贡献2，并使|min|'减少2
Case 4对|min|贡献2，并使|min|'减少1
因此，原数组arr[]中主元素的总数为:
|maj| = 2a + b
而所有次要元素的个数为:
|min| = b + 2c + 2d
Since |maj|> |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
因为我们从上面知道c + d
a > c + d =>
a > d =>
|maj|' > |min|'
因此maj仍然是新数组中的主元素。