Given an array of size n, find the majority element. The majority element is the element that appears more than ? n/2 ? times.
You may assume that the array is non-empty and the majority element always exist in the array.
题目: 找出出现次数超过一半的元素. 假设数组中一定有该元素.
思路: 参考 A Linear Time Majority Vote Algorithm http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html , 算法的简单演示: 演示链接 http://www.cs.utexas.edu/~moore/best-ideas/mjrty/example.html .
算法的基本思路为:
设置一个当前候选者, 表示当前便遍历过的元素中的最多数. 设置一个 count, 初始值为 0, 记录候选者比所有其他元素多出几个.
当 count= 0, 将下一个元素设置为候选者, 然后 count+1;
当 count 不等于 0, 如果下一个元素 = 候选者, 则 count+1, 否则 count-1.
遍历结束后, 候选者即为出现次数超过一半的元素. 代码如下:
- class Solution {public int majorityElement(int[] nums) {
- int count = 0;
- int candidate = 0;
- for(int i = 0; i < nums.length; ++i){
- if(count == 0){
- candidate = nums[i];
- }
- if(candidate == nums[i])
- ++count;
- else
- --count;
- }
- return candidate;
- }
- }
参考: https://www.cnblogs.com/JimmyTY/p/5020871.html
来源: http://www.bubuko.com/infodetail-2588214.html