Finding majority element in unsorted array - PrismoSkills

Finding majority element in unsorted array - PrismoSkills
If the array were sorted, then majority element could be found by a modified binary search in log N time
If its unsorted, then since the majority element occurs n/2+1 times, we can see that its count can not decrease to 0 if we increment count on its occurrence and decrement count on its absence.
So the following code can help us find the majority element:
http://www.cnblogs.com/chkkch/archive/2012/11/22/2782198.html
方法2：用qsort的partition的方法找出第k大数，k就是数组中间的数，对于n为偶数是中间两个的任意一个数，奇数的话就只有一个。那么，因为数的个数超过一半，那么中间那个数肯定是超过一半的那个数，否则这个数就不存在了。最后遍历一遍数组来验证一下。partition的平摊复杂度为O(n)。最后算法总体复杂度O(n)

7 void partition(int num[], int left, int right, int k)
 8 {
 9     if (left >= right)
10         return;
11 
12     int randNum = left + (rand() % (right - left + 1));
13 
14     int t = num[left];
15     num[left] = num[randNum];
16     num[randNum] = t;
17 
18     int i = left;
19     int j = right;
20 
21     int key = num[left];
22 
23     while(i <= j)
24     {
25         if (num[i] <= key)
26             i++;
27         else
28         {
29             int t = num[j];
30             num[j] = num[i];
31             num[i] = t;
32 
33             j--;
34         }
35     }
36 
37     num[left] = num[j];
38     num[j] = key;
39 
40     if (j == k)
41         return;
42     else
43     {
44         partition(num, left, j - 1, k);
45         partition(num, j + 1, right, k);
46     }
47 }

这道题可以分两种方法做。方法1：类似于消除原理，既然某个数字大于长度的一半，那么我们就遍历数组，如果两个数不相等则消除，最后剩下的数就是我们要的。当然如果不存在这样的数，这是不行的。所以最后要再遍历一遍验证这个数的出现次数是否大于数组的一半。
Read full article from Finding majority element in unsorted array - PrismoSkills