【20】剑指offer——数组中出现次数超过一半的数字【最全题解】
题目描述数组中有一个数字出现的次数超过数组长度的一半请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次超过数组长度的一半因此输出2。如果不存在则输出0。解题思路思路1我首先想到的利用map容器因为map容器是具有两个数的对应关系可以分别表示数字和数字出现的次数然后统计出现的次数从而找到满足条件的答案。代码如下class Solution { public: int MoreThanHalfNum_Solution(vectorint numbers) { int len numbers.size(); if (len 0) return 0; mapint, int ans; mapint, int::iterator it; for (int i 0; i len; i){ it ans.find(numbers[i]); if (it ! ans.end()){ ans[numbers[i]]; } else { ans[numbers[i]] 1; } } int ans_first 0; int ans_second 0; for (it ans.begin(); it ! ans.end(); it){ if ((*it).second ans_second){ ans_first (*it).first; ans_second (*it).second; } else{ continue; } } if (ans_second (len) / 2){ return ans_first; } else{ return 0; } } };然后我看到了题解找到了一个和我思路一致的答案但是明显代码比我简单很多也更加易读在这里分享链接https://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163?fdiscussion 来源牛客网 class Solution { public: int MoreThanHalfNum_Solution(vectorint numbers) { int n numbers.size(); //map 记录出现次数 mapint, int m; int count; for (int i 0; i n; i) { count m[numbers[i]]; if (count n/2) return numbers[i]; } return 0; } };思路2利用快排的思想首先进行排序之后取排序后的数组中间的数字即可好处是简单易懂缺点是时间复杂度过高排序耗时。代码如下class Solution { public: int MoreThanHalfNum_Solution(vectorint numbers) { int len numbers.size(); if (len 0) return 0; //if (len 1) return numbers[0]; sort(numbers.begin(), numbers.end()); int ans numbers[(len)/2]; int count 0; for (int i 0; i len; i){ if (numbers[i] ans){ count; } if (count len / 2){ return ans; } } return 0; } };思路3这个思路非常巧妙但是非常变态。因为是数组中大于一半长度大小的元素所以当第一次遍历数组的时候记录重复元素和出现次数对数组元素两两进行比较如果相同则出现次数加一如果不同则出现次数减一如果出现次数为0则替换重复元素为新比较的元素出现次数设为1如果数组中存在大于一半长度的元素则遍历一遍之后一定会找出。然后再遍历一遍数组记录其出现的次数如果大于一半长度则返回。代码如下class Solution { public: int MoreThanHalfNum_Solution(vectorint numbers) { int len numbers.size(); if (len 0) return 0; int ans numbers[0]; int count 1; for (int i 1; i len; i){ if (numbers[i] ans){ count ; } else { count --; } if (count 0){ ans numbers[i]; count 1; } } count 0; for (int i 0; i len; i){ if (numbers[i] ans) { count ; } if (count len / 2){ return ans; } } return 0; } };苦心人天不负卧薪尝胆三千越甲可吞吴我爱算法
)
