刷题记录——剑指 Offer 39. 数组中出现次数超过一半的数字

2021/9/27

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

限制：
1 <= 数组长度 <= 50000

思路

1.先对数组进行排序，这样相同的数就可以挨在一起。
2.遍历排序后的数组，若前后两数相同就对计数器count++，当count>len/2时，就跳出循环，返回nums[i].前后两数不相等时，重置count为1.

代码

class Solution {
public:
int majorityElement(vector<int>& nums) {
if(nums.size()<1 || nums.size()>50000)
return -1;
sort(nums.begin(), nums.end());
int count = 1;
int target = nums[0];
for(int i=0; i<nums.size(); i++){
if(count > nums.size()/2){
target = nums[i];
break;
}
if(i<nums.size()-1 && nums[i] == nums[i+1])
count++;
if(i<nums.size()-1 && nums[i] != nums[i+1])
count = 1;
if(i>0 && i == nums.size()-1 && nums[i]!=nums[i-1])
count = 1;
}
return target;
}
};

总结反思

这个题的解题思路有很多：哈希表、摩尔投票、排序法、计数法······
总结一下后来用摩尔投票法实现的代码（摩尔投票法的时间复杂度：O(n)，空间复杂度：O(1)，时间复杂度和空间复杂度都较低）
思路：
遍历数组，用计数器count计数，设置变量cur用来存放目标值，当当前遍历到的数字nums[i]和cur相等时count加一，否则count减一；当count减为0时，重新设置cur为nums[i].

class Solution {
public:
int majorityElement(vector<int>& nums) {
int count = 0;
int cur = 0;
for(int i=0; i<nums.size(); i++){
if(count == 0)
cur = nums[i];
if(cur == nums[i])
count++;
else
count--;
}
return cur;
}
};

最后

以上就是帅气汽车为你收集整理的刷题记录——剑指 Offer 39. 数组中出现次数超过一半的数字的全部内容，希望文章能够帮你解决刷题记录——剑指 Offer 39. 数组中出现次数超过一半的数字所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。