题目

给定一个整型数组，找出主元素，它在数组中的出现次数严格大于数组元素个数的二分之一。

 样例

给出数组[1,1,1,1,2,2,2]，返回 1

思路

首先 发现所给的数组是顺序排列好的。

用动态规划的思路解决  可以把时间复杂度减小到O(n)空间复杂度O(1)

C++代码

1 int majorityNumber(vector
       
         nums) { 2         // write your code here 3         int count = 1; 4         int i; 5         for(i = 1; i < nums.size(); ++i) 6         { 7             if(nums[i] == nums[i - 1]) count++; 8             else  9             {10                 if(double(count)/nums.size() > 0.5) break;11                 count = 1;12             }13             14         }15         return nums[i - 1];16     }