題目描述
陣列中有一個數字出現的次數超過陣列長度的一半，請找出這個數字，例如輸入一個長度為9的陣列{1,2,3,2,2,2,5,4,2}，由于數字2在陣列中出現了5次，超過陣列長度的一半，因此輸出2，如果不存在則輸出0，
思路
思路就是摩爾投票法，原理非常簡單，
這里推薦一個幫助大家理解的例子，
核心就是對拼消耗，玩一個諸侯爭霸的游戲，假設你方人口超過總人口一半以上，并且能保證每個人口出去干仗都能一對一同歸于盡，最后還有人活下來的國家就是勝利，那就大混戰唄，最差所有人都聯合起來對付你（對應你每次選擇作為計數器的數都是眾數），或者其他國家也會相互攻擊（會選擇其他數作為計數器的數），但是只要你們不要內斗，最后肯定你贏，最后能剩下的必定是自己人，
鏈接：https://www.zhihu.com/question/49973163/answer/617122734
來源：知乎
最優解
- 時間O(n)空間O(1)
import java.util.Arrays;
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
int value = 0;
int count = 0;
for (int i = 0; i < array.length; i++) {
if (count == 0) {
value = array[i];
count++;
}else {
if (value == array[i]) {
count++;
}else {
count--;
}
}
}
if (count == 0) {
return 0;
}
count = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] == value) {
count++;
}
}
return count > array.length/2 ? value : 0;
}
}
發現foreach比用fori多兩毫秒，后來查資料了解了一下
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/89333.html
標籤：其他
上一篇：hadoop的spark問題