OJ练习35——T169 Majority Element

得到一串整数的主元素。

主元素即出现次数多于n/2(下界)的数。

【思路】1.用map<int,int>类型，记录每个数据出现的次数。

2.用博主陆草纯的算法，当连续两数不同时，就把两者抵消掉，剩下的就是主元素。

【my code】

int majorityElement(vector<int>& nums) {
        map<int,int>m;
        int num=nums.size()/2;
        for(int i=0; i<nums.size(); i++){
            m[nums[i]]++;
            if(m[nums[i]]>num)
                return nums[i];
        }
    }

【other code】

int majorityElement(vector<int>& nums) {
        int nTimes = 0;
        int candidate = 0;
        for(int i = 0; i < nums.size(); i ++)
        {
            if(nTimes == 0)
            {
                candidate = nums[i];
                nTimes = 1;
            }
            else
            {
                if(candidate == nums[i])
                    nTimes ++;
                else
                    nTimes --;
            }
        }
        return candidate;
    }

【评价】

1.我的方法耗时40ms，排名较为靠后。

2.陆神算法用时25ms，排名前排。但是陆神的算法适用于该数列已经排序的情况，说明题目是有这个条件的！

先想到这里。