4-11. Design an O(n) algorithm that, given a list of n elements, finds all the elements that appear more than n / 2 times in the list. Then, design an O(n) algorithm that, given a list of n elements, finds all the elements that appear more than n / 4 times.

gistfile1.java

/**
 * @param in - input dataset containing elements we'd like to search through
 * @param k - denominator to indicate desired occurrence of elements (e.g. with n/2, k = 2)
 * @return We will return all elements whose frequency is greater than n/k.
 */
public static ArrayList<Integer> getFrequentElements(int[] in, int k){

    Map<Integer, Integer> freqMap = new HashMap<Integer, Integer>();
    ArrayList<Integer> out = new ArrayList<Integer>();

    for(int i=0; i<in.length; i++){
        if(freqMap.containsKey(in[i])){
            freqMap.put(in[i], freqMap.get(in[i]) + 1 );
        } else {
            freqMap.put(in[i], 1);
        }
    }

    int maxFrequency = in.length/k;
    for(Map.Entry<Integer, Integer> entry : freqMap.entrySet()){
        if(maxFrequency < entry.getValue()){
            out.add(entry.getKey());
        }
    }

    return out;
}


/** Test using main function **/
public static void main(String[] args){

    int[] a = {2, 5, 2, 7, 2, 7, 1, 2, 7, 8, 2, 2, 2, 7, 7, 7};

    ArrayList<Integer> frequentElements = getFrequentElements(a, 4);

    for(Integer i : frequentElements){
        System.out.println(i);
    }

}