lintcode.46 主元素

2018-06-17 21:58:22来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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

 

注意事项

You may assume that the array is non-empty and the majority number always exist in the array.

样例

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

挑战

要求时间复杂度为O(n),空间复杂度为O(1)

 

这道题要求O(n),肯定是遍历一遍出结果。然而主元素一定大于长度的一半。由此,主元素减去其他所有数的数量还是会大于0。

 

class Solution {
public:
    /*
     * @param nums: a list of integers
     * @return: find a  majority number
     */
    int majorityNumber(vector<int> &nums) {
        // write your code here
        int s=nums.size();
        int res=nums[0];
        int cnt=1;
        for(int i =1;i<s;i++)
        {
            if(res==nums[i])
                cnt++;
            else
                cnt--;
            if(cnt<=0){
                res=nums[i];
                cnt=0;
            }
        }
        return res;
    }
};

  

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:hdu 1754 I hate it

下一篇:hdu 6107--Typesetting(倍增)