https://www.cnblogs.com/evasean/p/7273857.html
https://raw.githubusercontent.com/phareskrad/algs4/master/jobinterviewquestions/QuickSort.java
Decimal dominants. Given an array with n keys, design an algorithm to find all values that occur more than n/10 times. The expected running time of your algorithm should be linear.
分析：
直观上将n个元素遍历一遍，并记录每个元素出现的次数就可以实现，虽然时间复杂度是O(n)，但是空间复杂度却高达n，这肯定不是该题目的初衷。对于n个元素来说，出现n/10次的元素最多有10个，那么出现超过n/10次的元素最多不超过9个，所以需要9个额外空间auxs就能满足需求。
这9个辅助空间aux怎么使用呢？可采用俄罗斯方块的消去一行的思路。只不过这里消去一行的情况是该行中元素各不相同。
1. 遍历数组array中的每个元素array[i]
2. 如果array[i]在aux中存在，将其在aux中的计数+1
3. 如果array[i]在aux中不存在
3.1 如果aux未满，将其放入aux中，并记录其个数为1
3.2 如果aux已满，将aux中已经存在的各个元素的计数都减去1，直到某个元素的个数变成0，将array[i]放入aux中该位置处，并记录其个数为1
4. 出现次数超过n/10的元素在array遍历完了之后，还会继续存在于aux中，当然aux中可存在着位于array后方但出现次数不满足要求的元素。这时只需要遍历aux的同时再遍历一遍array，记录aux中各个元素在array中出现的次数，将其中出现次数真正超过n/10的元素找出来即可。
Naively, we could just count the number of occurrences of each elements.
- define a hash map from the values to the number of occurrence of those values in the array.
- iterate through the array and populate the hash map.
- iterate through the hash map and get keys with values greater than or equal to n/10.
This takes ~N time and ~N space.
Solution 2
We can optimize the first solution to reduce the memory usage. The key point leading to this optimization is that if the array is of size n, there can be at most 9 elements that occur more than n/10 times. If we suppose that the array had 10 elements that occur more than n/10 times, then we will have more than n elements in the array, which is a contradiction.
With this realization in mind, we can solve the problem using 9 buckets with Boyer-Moore majority vote algorithm.
Basically, we can remember 9 elements along with the number of times they have been seen so far in a loop. When a remembered element is seen, its count is incremented. If an element which is not remembered is seen, we fit it into a slot if one is free. If no slot is free, subtract 1 from all counts. If the count is 0, forget the element.
This takes ~N time and ~1 space.
Solution 3
We can also use a selection algorithm to solve the problem in a linear time. If we imagine the array was sorted in a descending order, we can narrow our candidates to 9 elements, namely (n/10)-th, (2n/10)-th, … (9n/10)-th elements.
In this imaginary sorted version of the array, any elements left to (n/10)-th array cannot occur more than n/10 times because there won’t be enough room.
Using QuickSelect, we can get (n/10)-th largest element from the array without sorting the entire array. After checking if (n/10)-th largest element is decimal dominant, we apply the same procedure to the array including and to the right side of (n/10)-th largest element. This means we check for (2n/10)-th largest element, and so on.
This takes ~N time (9 calls to QuickSelect) and ~1 space.
public DecimalDominants(int[] a, int k) {
A = a;
N = a.length;
K = k;
buildCounts(a);
}
private void buildCounts(int[] a) {
for (int i = 0; i < N; i++) {
if (counts.containsKey(i)) counts.put(i, counts.get(i) + 1);
else counts.put(i, 1);
if (counts.keySet().size() >= K) removeCounts();
}
}
private void removeCounts() {
for (int k : counts.keySet()) {
int c = counts.get(k);
if (c > 1) counts.put(k, c - 1);
else counts.remove(k);
}
}
public Iterable<Integer> find() { //brute force
Bag<Integer> result = new Bag<Integer>();
for (int k : counts.keySet()) {
if (count(k) > N/K) result.add(k);
}
return result;
}
private int count(int k) {
int count = 0;
for (int i = 0; i < N; i++) {
if (A[i] == k) count++;
}
return count;
}
}
7 public class ElemsMoreThanNDivTenTimes { 8 9 private class Element{//辅助空间元素定义，用来记录元素值及其出现次数 10 public int element; 11 public int count; 12 public Element(int e,int c){ 13 this.element = e; 14 this.count = c; 15 } 16 }; 17 private Element[] elems = new Element[9]; //申请9个辅助空间 18 19 20 public ArrayList<Integer> findElements(int[] arrays){ 21 int n = arrays.length; 22 for(int k=0;k<9;k++){ 23 elems[k] = new Element(0,0); //辅助空间初始化 24 } 25 for(int i=0;i<n;i++){ 26 int index = findIndex(arrays[i]); 27 if(index >= 0) 28 elems[index].count ++; 29 else 30 addToElems(arrays[i]); 31 } 32 return verifyElems(arrays); 33 } 34 35 private int findIndex(int e){ 36 for(int k = 0; k<9;k++){ 37 if(elems[k].element == e) 38 return k; 39 else if(elems[k].count == 0){ 40 elems[k].element = e; 41 return k; 42 } 43 } 44 return -1; 45 } 46 private void addToElems(int e){ 47 boolean insertFlag = false; 48 while(!insertFlag){ 49 for(int k=0; k<9;k++){ 50 elems[k].count --; 51 if(elems[k].count <= 0){ 52 elems[k].element = e; 53 elems[k].count = 1; 54 insertFlag = true; 55 break; 56 } 57 } 58 } 59 } 60 private ArrayList<Integer> verifyElems(int[] arrays){ 61 int n = arrays.length; 62 for(int k = 0; k< 9; k++){ 63 elems[k].count = 0; 64 for(int i = 0; i< n;i++){ 65 if(arrays[i]==elems[k].element) 66 elems[k].count++; 67 } 68 } 69 ArrayList<Integer> elemList = new ArrayList<Integer>(); 70 for(int k = 0; k< 9; k++){ 71 if(elems[k].count > n/10) 72 elemList.add(elems[k].element); 73 } 74 return elemList; 75 }
