題一：數(shù)組arr全闷，打印出數(shù)組中個(gè)數(shù)大于一半的數(shù)
public int solve(int[] arr) {
int num = 0, time = 0;
for (int i = 0; i < arr.length; i++) {
if (time == 0) {
num = arr[i];
time = 1;
}else if (arr[i] == num) {
time++;
}else {
time--;
}
}
time = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == num) time++;
}
if (time > arr.length/2) {
return num;
}else {
System.out.println("沒(méi)有個(gè)數(shù)大于一半的數(shù)");
}
return -1;
}
public static void main(String[] args) {
Page343 instance = new Page343();
int[] nums = {1,2,3,4,2,3,1,5};
int[] nums2 = {1,2,3,2,1,2,2,1,2,3,2,6,2,7,2,3,2,2,2,9,2,2,7,5};
int[] nums3 = {1};
int[] nums4 = {1,2,3,1};
int result = instance.solve(nums);
System.out.println(result);
result = instance.solve(nums2);
System.out.println(result);
result = instance.solve(nums3);
System.out.println(result);
result = instance.solve(nums4);
System.out.println(result);
}
num記錄數(shù)字，time記錄個(gè)數(shù)狼犯；遍歷過(guò)程中不相同的相互抵消凡纳。
題二：數(shù)組arr窃植，打印個(gè)數(shù)大于N/k的數(shù)
public void solve(int[] arr, int k) {
Map<Integer, Integer> map = new HashMap<>();
// 首先找到k-1個(gè)不同的數(shù)，并記錄它們出現(xiàn)的次數(shù)荐糜，繼續(xù)向后遍歷
// 若下一個(gè)數(shù)map里有則將該數(shù)個(gè)數(shù)即value+1巷怜，否則 if (map里個(gè)數(shù)==k-1)則全部個(gè)數(shù)-1
// else 將該數(shù)加入map
for (int anArr : arr) {
Integer value;
if ((value = map.get(anArr)) != null) {
map.replace(anArr, value + 1);
} else {
if (map.size() == k - 1) {
subtractAll(map, k);
} else {
map.put(anArr, 1);
}
}
}
map.keySet().forEach(integer -> map.replace(integer, 0));// 將map里所有數(shù)的個(gè)數(shù)即value清零
// 再次循環(huán)統(tǒng)計(jì)map里數(shù)字的真正個(gè)數(shù)
for(int num : arr) {
Integer val;
if ((val = map.get(num)) != null) {
map.replace(num, val+1);
}
}
map.forEach((key, value) -> {
if (value > arr.length / k) {
System.out.print(key + " ");
}
});
}
// 將map里全部數(shù)字的value值減1，減1后若value==0暴氏，則刪除該鍵
private void subtractAll(Map<Integer, Integer> map, int k) {
List<Integer> list = new ArrayList<>();
map.forEach((integer, integer2) -> {
if (integer2 == 1) {
list.add(integer);
}else {
map.replace(integer, integer2-1);
}
});
if (list.size() != 0) {
for (Integer key : list) {
map.remove(key);
}
}
}
public static void main(String[] args) {
Page343Advance instance = new Page343Advance();
int[] arr = {1,2,3,2,2,1,1,2,3,3,3,1,5,6,7,6,5,5,6,7,3,2,1,8,9,11,24,44};
int[] arr1 = {1,2,3,4,5,2,2,1};
int[] arr2 = {2};
instance.solve(arr, 8);
System.out.println();
instance.solve(arr1, 4);
System.out.println();
instance.solve(arr2, 1);
}
給定一個(gè)整形數(shù)組和K延塑，打印所有大于N/k的數(shù)字
整體解題思路是沿著上一題：整形數(shù)組arr，打印出現(xiàn)次數(shù)大于一半（N/2）的數(shù)
在上一題中使用一個(gè)num與time來(lái)記錄數(shù)字及其出現(xiàn)的次數(shù)偏序，time==0页畦，則刪除num中的值胖替；就是相互抵消大于一半的數(shù)一定會(huì)最后留下來(lái)研儒；
這一題是上一題的擴(kuò)展，大于N/k的數(shù)独令，就用k-1個(gè)num與time來(lái)記錄端朵，即map大小為k-1
1，當(dāng)map不滿時(shí)就將該數(shù)加進(jìn)map燃箭，個(gè)數(shù)為1冲呢；
2，當(dāng)map中存在該數(shù)則其time+1招狸；
3敬拓，當(dāng)map滿了且沒(méi)有該數(shù)，則將map中所有value減1裙戏，等于0的則刪除該鍵值對(duì)乘凸。
為什么map剩下的數(shù)字里一定有大于N/k的數(shù)？因?yàn)橹挥挟?dāng)map.size==k-1的情況下才會(huì)減1累榜，那么這一來(lái)就變成最少k個(gè)數(shù)才會(huì)減1营勤，那么你N個(gè)數(shù)，最多減N/K，所以大于N/k的數(shù)一定會(huì)剩下來(lái)
