链接
我写的代码:
class Solution {
public:int majorityElement(vector<int>& nums) {if(nums.size()==1)return nums[0];sort(nums.begin(),nums.end());int n = nums.size();int res = 0;for(int i = 0;i<n;i++){int j = i;while(j+1<n&&nums[j]==nums[j+1])++j;if((i!=j)&&(j-i+1)>n/2){res = nums[j];break;}}return res;}
};
我模仿的优秀的代码:
class Solution {
public:int majorityElement(vector<int>& nums) {int r,t = 0;for(const auto&e:nums){if(t==0){r = e;++t;}else{if(r==e){++t;}else{--t;}}}return r;}
};
优秀的代码本身:
class Solution {
public:int majorityElement(vector<int>& nums) {int r,c = 0;for(auto x:nums){if(!c)r = x,c = 1;else if(r==x)++c;else --c;}return r;}
};
用 r 记录一个数,t 记录一个次数,遍历这个数组,如果遇到了和 r 相同的值,++t;说明 r 又多了一个,遇到了不同的数,就--t ;说明 r 被抵消了一个,而当t 减到0的时候,我们就用当前遍历到的元素当作新的r 。
为什么可以这样做呢?因为题目中说了:存在一个元素出现次数大于n/2 ;
我们选择一个数当作r 也就是答案,存在两种可能:1)这就是真正的答案2)这是假的答案,真正的r 我们没有找到。
那么我们继续遍历即可,如果它是真正的答案,那么遍历完所有元素,它肯定还是r 没变,因为他出现的次数超过了数组的一半,
如果他不是真正的答案,那么它会因为数量不足而被数量超过数组一半的真正的答案代替掉。