Given an array of of size n and a number k, find all elements that appear more than n/k times | GeeksforGeeks
Given an array of size n, find all elements in array that appear more than n/k times. For example, if the input arrays is {3, 1, 2, 2, 1, 2, 3, 3} and k is 4, then the output should be [2, 3]. Note that size of array is 8 (or n = 8), so we need to find all elements that appear more than 2 (or 8/4) times. There are two elements that appear more than two times, 2 and 3.
Similar as Solution to Majority Element
-- We can use (K-1) sized HashMap.
Given an array of size n, find all elements in array that appear more than n/k times. For example, if the input arrays is {3, 1, 2, 2, 1, 2, 3, 3} and k is 4, then the output should be [2, 3]. Note that size of array is 8 (or n = 8), so we need to find all elements that appear more than 2 (or 8/4) times. There are two elements that appear more than two times, 2 and 3.
Let N = size of the input array A.
Now we need to find all the elements in the array which occur more than (N/K) times in the input Array A.
maintain a Map (Key=A[i], and value is the frequency of Key in array A so far).
as soon as the size of the Map reaches K, decrement the value of all the Keys by 1, if the value is 1, then after decrementing it will be 0 - Delete those keys from Map.
At max you will have to do (N/K) deletions.
In the end you will be left with atmost (K-1) unique Keys - which are candidate answers.
Now again re-iterate through the array A and report the Keys whose frequency is greater than (N/K).
-- We can use (K-1) sized HashMap.
We can solve the above problem in O(nk) time using O(k-1) extra space. Note that there can never be more than k-1 elements in output.
1) Create a temporary array of size (k-1) to store elements and their counts (The output elements are going to be among these k-1 elements). Following is structure of temporary array elements.
struct eleCount {
int element;
int count;
};
struct eleCount temp[];
This step takes O(k) time.
2) Traverse through the input array and update temp[] (add/remove an element or increase/decrease count) for every traversed element. The array temp[] stores potential (k-1) candidates at every step. This step takes O(nk) time.
3) Iterate through final (k-1) potential candidates (stored in temp[]). or every element, check if it actually has count more than n/k. This step takes O(nk) time.
struct eleCount{ int e; // Element int c; // Count};// Prints elements with more than n/k occurrences in arr[] of// size n. If there are no such elements, then it prints nothing.void moreThanNdK(int arr[], int n, int k){ // k must be greater than 1 to get some output if (k < 2) return; /* Step 1: Create a temporary array (contains element and count) of size k-1. Initialize count of all elements as 0 */ struct eleCount temp[k-1]; for (int i=0; i<k-1; i++) temp[i].c = 0; /* Step 2: Process all elements of input array */ for (int i = 0; i < n; i++) { int j; /* If arr[i] is already present in the element count array, then increment its count */ for (j=0; j<k-1; j++) { if (temp[j].e == arr[i]) { temp[j].c += 1; break; } } /* If arr[i] is not present in temp[] */ if (j == k-1) { int l; /* If there is position available in temp[], then place arr[i] in the first available position and set count as 1*/ for (l=0; l<k-1; l++) { if (temp[l].c == 0) { temp[l].e = arr[i]; temp[l].c = 1; break; } } /* If all the position in the temp[] are filled, then decrease count of every element by 1 */ if (l == k-1) for (l=0; l<k; l++) temp[l].c -= 1; } } /*Step 3: Check actual counts of potential candidates in temp[]*/ for (int i=0; i<k-1; i++) { // Calculate actual count of elements int ac = 0; // actual count for (int j=0; j<n; j++) if (arr[j] == temp[i].e) ac++; // If actual count is more than n/k, then print it if (ac > n/k) cout << "Number:" << temp[i].e << " Count:" << ac << endl; }}
思路和Majority NumberII 一样，维护k-1个candidate 在map里面，key为数字值，value为出现次数。先找到这k-1个candidate后，扫描所有元素，如果该元素存在在map里面，update map；如果不存在，1： 如果map里面有值为count= 0，那么删除掉这个元素，加入新元素；2：map里面没有0出现，那么就每个元素的count--
剩下的map里面的值都有可能是majority，所以重新扫描数组，记录下每一个元素出现次数，次数最大的就是majority
http://blog.csdn.net/nicaishibiantai/article/details/43636799
https://github.com/shawnfan/LintCode/blob/master/Java/Majority%20Number%20III.java
Lintcode: There is only one majority number in the array.
https://github.com/shawnfan/LintCode/blob/master/Java/Majority%20Number%20III.java
Lintcode: There is only one majority number in the array.
7 public int majorityNumber(ArrayList<Integer> nums, int k) { 8 if (nums==null || nums.size()==0) return 0; 9 10 int len = nums.size(); 11 Map<Integer,Integer> nMap = new HashMap<Integer,Integer>(); 12 nMap.put(nums.get(0),1); 13 for (int i=1;i<len;i++) 14 if (nMap.containsKey(nums.get(i))){ 15 int val = nMap.get(nums.get(i))+1; 16 nMap.put(nums.get(i),val); 18 } else { 19 //if the number of existing numbers is less than k-1, then just add one. 20 if (nMap.size()<k-1){ 21 nMap.put(nums.get(i),1); 22 } else { 23 List<Integer> keyList = new ArrayList<Integer>(); 24 //decrease the value of every key by 1. 25 for (Map.Entry en : nMap.entrySet()){ 26 int key = (int) en.getKey(); 27 int value = (int) en.getValue(); 28 value--; 29 if (value==0) keyList.add(key); 30 nMap.put(key,value); 31 } 32 for (int key : keyList) nMap.remove(key); 33 } 34 } 35 36 for (Map.Entry en: nMap.entrySet()) en.setValue(0); 37 int num = 0, count = 0; 38 for (int i=0;i<len;i++) 39 if (nMap.containsKey(nums.get(i))){ 40 int val = nMap.get(nums.get(i))+1; 41 if (val>count){ 42 num = nums.get(i); 43 count = val; 44 } 45 nMap.put(nums.get(i),val); 46 } 47 return num; 48 49 }
http://karmaandcoding.blogspot.com/2011/12/finding-repeated-elements-in-array.html
http://www.shuatiblog.com/blog/2014/06/28/Majority-Number-III/
http://www.shuatiblog.com/blog/2014/06/28/Majority-Number-III/
Another idea suggest by G4G is a mechanism similar to the famous Tetris Game. The size of the buffer is k. The buffer is full, we remove all items by counter of 1. When counter reach 0, remove that item. In this way, the elements left in the buffer are the majority numbers.
This method is also used in counting highly-frequent string keywrods.
