Majority Element最优解看不懂(不是Moore Voting), 求大神指点思路

代码是 leetcode 提交的时候直接点第一名点出来的. 作者应该是个中国人, 只有代码, 速度确实是第一名1ms, 比moore voting快, 但是原理看不懂, 希望大神指点一下:

1. 
   
2. /*
   
3. Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
   
4. 
   
5. You may assume that the array is non-empty and the majority element always exist in the array.
   
6. */
   
7. 
   
8. public class MajorityElement {
   
9.     public int majorityElement(int[] nums) {
   
10.         return maj(nums, nums.length);
    
11.     }
    
12. 
    
13.     public int maj(int[] nums, int n) {
    
14.         if (n == 1 || n == 2) return nums[0];
    
15.         int p = 0;
    
16.         for (int i = 0 ; i < n; i = i + 2) {
    
17.             if (i == n - 1 || nums[i] == nums[i + 1]) {
    
18.                 nums[p++] = nums[i];
    
19.             }
    
20.         }
    
21.         return maj(nums,p);
    
22.     }
    
23.        
    
24.     public static void main(String[] args) {
    
25.         MajorityElement tester = new MajorityElement();
    
26.         int[] input1 = {1,2,1,3,1,4,1};
    
27.         System.out.println(tester.majorityElement(input1));
    
28.     }
    
29. }
    

复制代码

comment里面有题目简介.

主要是不知道这个算法背后的原理是什么? 为什么这个算法就是对的? 和一个认识的大神讨论过, 不太理解这个算法的 correctness, 但是就是举不出反例.

楼主引用的这个解法适合1,2,1,2,1,2,1,2,...这种交替型的workload。如果输入数据是1,1,1,1,...,2,2,2,2,...这种连续一大段都是同一个数的workload，那么这种算法会相对比较慢。所以它的速度最快大概是因为LeetCode的测试数据比较对它胃口...

要证明其正确性，本质上是要证明如下定理：
定理1：给定一个长度为n>2的数组nums[0] ... nums[n-1]，其中包含有Majority Element K。那么执行完所给代码的第15~20行后，nums[0] ... nums[p-1]中包含Majority Element K。

然后每次调用maj都有p <= n/2，递归调用就行了，worst case下要递归log(n)层（例如：所有n个元素都是K的情况）。

下面来证明定理1，我们可以用反证法。
---------------------------------------------------
定理1的证明：
假设执行完所给代码的15~20行后，nums[0] ... nums[p-1]中包含u个K，v = p - u个其他元素，且u <= v（即K不是Majority Element）。

那么，考虑n的奇偶：
Case (1): n为偶数
由17~18行的代码易知原来的nums[0] ... nums[n-1]数组中至多有 S = u*2 + (n/2 - p)个K。
注意到u*2 - p = u - v <= 0，所以S <= n/2，这与前提条件“K在原来的数组中是Majority Element”矛盾。

Case (2): n为奇数
这里再细分为两种情况：
Case (2.1): nums[n-1] == K
    由17~18行的代码易知原来的nums[0] ... nums[n-1]数组中至多有 S = (u-1)*2 + ((n+1)/2 - p)个K。
    那么化简S = (n-3)/2 + (u-v) < (n-1)/2，这与前提条件“K在原来的数组中是Majority Element”矛盾。
Case (2.2): nums[n-1] != K
    由17~18行的代码易知原来的nums[0] ... nums[n-1]数组中至多有 S = u*2 + ((n-1)/2 - p)个K。
    那么化简S = (n-1)/2 + (u-v) <= (n-1)/2，这与前提条件“K在原来的数组中是Majority Element”矛盾。

所以任何情况下假设都不成立，也就是说执行完15~20行后，K在nums[0] ... nums[p-1]中必然是Majority Element。▢
---------------------------------------------------

楼主可以看看这个http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

乌云典当记 发表于 2017-6-28 00:34
楼主可以看看这个http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

这个算法不是moore voting. moore voting我是懂得. 这个算法比moore voting还快.

magicsets 发表于 2017-6-28 08:30
楼主引用的这个解法适合1,2,1,2,1,2,1,2,...这种交替型的workload。如果输入数据是1,1,1,1,...,2,2,2,2,... ...

非常感谢你的分享, 你这个 invariant 一点出来就豁然开朗了. 不知道能不能加你一下的个人联系方式? 希望以后有更多的和你学习的机会.

补充内容 (2017-7-3 05:32):
已勾搭上大神