陣列中有一個數字出現的次數超過陣列長度的一半，請找出這個數字，例如輸入一個長度為 9 的陣列 {1,2,3,2,2,2,5,4,2}，由于數字 2 在陣列中出現了 5 次，超過陣列長度的一半，因此輸出 2，如果不存在則輸出 0
解法一
對陣列排序，如果符合條件的數存在，則一定是陣列中間那個數，代碼就不寫了，
解法二
利用 Map 存值，找出存在最多的數字，若大于長度的一半，回傳此數，否則回傳 0
import java.util.Map;
import java.util.HashMap;
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array == null || array.length == 0) {
return 0;
}
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < array.length; i++) {
if(map.containsKey(array[i])) {
map.put(array[i], map.get(array[i]) + 1);
} else {
map.put(array[i], 1);
}
}
for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
if(entry.getValue() > (array.length / 2)) {
return entry.getKey();
}
}
return 0;
}
}
解法三
注意到目標數超過陣列長度的一半，如果對陣列同時去掉兩個不同的數字，到最后剩下的數就是該數字，實作的方式采用陣地攻守思想：
- 第一個數字作為第一個士兵，守陣地，count = 1
- 遇到相同元素，count++
- 遇到不相同元素，即為敵人，同歸于盡，count--
- 遇到 count = 0 的情況，又以新的 i 值作為守陣地的士兵，繼續下去，到最后還留在陣地上的士兵，有可能是我們希望的元素
- 再加一次回圈，記錄這個士兵的個數看是否大于陣列一半即可
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array == null || array.length == 0) {
return 0;
}
int val = array[0];
int count = 1;
for(int i = 1; i < array.length; i++) {
if(count == 0) {
val = array[i];
count = 1;
} else if(val == array[i]) {
count++;
} else {
count--;
}
}
count = 0;
for(int i = 0; i < array.length; i++) {
if(val == array[i]) {
count++;
}
}
return (count > array.length / 2) ? val : 0;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/171046.html
標籤：其他