LintCode_46 主元素

题目

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

样例

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

思路

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

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

C++代码

 int majorityNumber(vector<int> nums) {

         // write your code here

         int count = ;

         int i;

         for(i = ; i < nums.size(); ++i)

         {

             if(nums[i] == nums[i - ]) count++;

             else

             {

                 if(double(count)/nums.size() > 0.5) break;

                 count = ;

             }

         }

         return nums[i - ];

     }

巴特西

LintCode_46 主元素

最新文章

热门文章