今天刷题刷到了一个有意思的算法
题目为求一个数组的众数
大概思路是:先选第一个数是candidate(众数),初始化count=0。从前往后遍历数组遇到与当前
candidate相等就count+1,不相等就count-1。当count == 0时 candidate等于当前数组遍历到的那个数。遍历结束candidate就是这个数组的众数。
emm...可能表述不太清楚,直接看代码吧
class Solution {
public int majorityElement(int[] nums) {
int count = 0;
Integer candidate = null;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
}
//作者:LeetCode-Solution
//链接:https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/
//来源:力扣(LeetCode)
//著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
没有一个梦想是傻逼的