CareerCup

The following algo may help
1.)Take a hash map with key as array element and value as its count.
2.)as u traverse the array update the map.
3.)the size of map should not exceed k.
4.)once the size of map is k and we encounter a new element which is not yet in the map, decrement the count of all the existing keys by 1.
5.) If there is a key with count 0, replace it with the new element, or replace the key with the lowest count with the new element.
6.)Repeat the above till all elements in array are done.
7.)Now what u have is a map with k elements, set count to 0. traverse the array again and update the count of the keys in map.
8.)check for count and if it exceeds k print it.

Hi vimalk179,

Can you please explain a bit more on below statement.
"if it appears more than
n
k
times in A."
more than nk or n/k?

public static <T extends Comparable<T>> void findKMajority2(T[] array, int k) {
		System.out.println("Finding " + k + " majority list: ");
		if (k == 0) {
			return;
		}
		if(k == 1) {
			Set<T> s = new HashSet(Arrays.asList(array));
			System.out.println(s);
			return;
		}
		Map<T, Integer> map = new HashMap<T, Integer>();
		for(int i = 0; i < array.length; i++) {
			T key = array[i];
			if(map.containsKey(key)) {
				Integer count = map.get(key);
				if(++count == k) {
					System.out.print("	" + key);
				}
				map.put(key, count++);
			}else {
				map.put(key, 1);
			}
		}
		System.out.println();
	}

The algo is O(nk). In the first pass u generate the map.
Now if ur map has k elements then u scan the array k times to make sure that the keys are repeated n/k times.
So the net time complexity is O(nk).

sort the array ...time complexity nlogn for sorting
then traverse the array to find if any number exist which appears more than (n/k) times in array. can be done in O(n) time.
so total time complexity nlogn + O(n)
correct me if i'm wrong.