星期三, 三月 02, 2016

169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than  n/2  times.

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

解题思路:

思路请看剑指offer的面试29.。。。。。

class Solution {

public:

    int majorityElement(vector<int>& nums) {

        int n=nums.size();

        if(n==1)return nums[0];

        int pre=nums[0];

        int cnt=1;

        for(int i=0;i<n;i++){

            if(nums[i]==pre)cnt++;

            else

                cnt--;

            if(cnt==0){

                pre=nums[i];

                cnt=1;

            }

        }

        return pre;

    }

};

 

 

没有评论:

发表评论