网页设计制作报价表_百度搜索网页版_优化师是做什么的_seo网站诊断文档案例

链接

我写的代码：

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 没变，因为他出现的次数超过了数组的一半，

如果他不是真正的答案，那么它会因为数量不足而被数量超过数组一半的真正的答案代替掉。