性质1： 如果存在主元素的话，主元素一定是中位数。
方法1：
使用快排O(nlogn)进行排序，找到中位数，然后判断首元素是否和中位数相等、以及尾元素是否和中位数相等。 如果有一个以上的相等，则存在主元素（中位数）。
方法2：
使用O(n)的选择算法找到中位数，然后再判断中位数是不是主元素。
方法3：
性质2：如果一个数组中有主元素，则同时删除两个不相等的值，这个主元素不会改变。
因此下面的代码就是不断的删除两个不等的值。然后测试剩下的最后一个元素是不是主元素。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <string> 5 #include <vector> 6 #include <cassert> 7 using namespace std; 8 9 int test_and_cal(int *a, int len) 10 { 11 int seed = a[0]; 12 int count = 1; 13 14 for (int i = 1; i < len; i++) 15 { 16 if (seed == a[i]) 17 count++; 18 else 19 { 20 if (count == 0) 21 { 22 seed = a[i]; 23 count = 1; 24 } 25 else 26 count--; 27 } 28 } 29 30 // justify seed.. 31 count = 0; 32 for (int i = 0; i < len; i++) 33 { 34 if (a[i] == seed) 35 count++; 36 } 37 if (count >= len / 2) 38 return seed; 39 return -1; // no main elements in the array... 40 } 41 42 int main(int argc, const char * argv[]) 43 { 44 int num[] = {2,3,1,2,2,2,5,4,2,2}; 45 cout << test_and_cal(num, sizeof(num) / sizeof(num[0])) << endl; 46 return 0; 47 }
转载于:https://www.cnblogs.com/leiatpku/p/3350508.html
