##題目描述 陣列中有一個數字出現的次數超過陣列長度的一半，請找出這個數字，例如輸入一個長度為9的陣列{1,2,3,2,2,2,5,4,2}，由于數字2在陣列中出現了5次，超過陣列長度的一半，因此輸出2，如果不存在則輸出0，
思路
使用pre記錄上一次訪問的值，count表明當前值出現的次數，下一個值和當前值相同count++，不同count--，減到0時更新pre，如果存在超過陣列長度一半的值，那么最后pre一定會是該值(也可能不存在)，
時間復雜度O(n)，空間復雜度O(1)，
代碼
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array == null || array.length == 0) return 0;
int count = 1;
int pre = array[0];
for(int i = 1; i < array.length; i++) {
if(array[i] == pre) {
count++;
} else {
count--;
if(count == 0) {
pre = array[i];
count = 1;
}
}
}
count = 0;
for(int i = 0; i < array.length; i++) {
if(array[i] == pre) {
count++;
}
}
return count > array.length / 2 ? pre : 0;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/85177.html
標籤：其他
上一篇：字串的排列