wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Array Frequency
        
(Message started by: johny_cage on Nov 24^th, 2007, 5:51am)

Title: Array Frequency
Post by johny_cage on Nov 24^th, 2007, 5:51am

Print the elements of an array in the decreasing frequency but the order should be the same.
Example : 2 5 2 8 5 6 8 8
output : 8 8 8 2 2 5 5 6

Title: Re: Array Frequency
Post by SMQ on Nov 26^th, 2007, 10:36am

Once again, in Java we can make use of the fact that a LinkedHashMap iterates in insertion order to provide an O(n) (average, since it uses a hash) time and O(n) space solution:

import java.util.LinkedHashMap; import java.util.ArrayList; import java.util.Map; class PrintByFreq { public static void printByFreq(Object [] array) { int maxCount = 0; LinkedHashMap<Object, Integer> counts = new LinkedHashMap<Object, Integer>(); for(int i = 0; i < array.length; i++) { int count = 1; if (counts.containsKey(array[i])) count = counts.get(array[i]) + 1; counts.put(array[i], count); if (count > maxCount) maxCount = count; } ArrayList<Object> [] byFreq = new ArrayList[maxCount + 1]; for(int n = 1; n <= maxCount; n++) byFreq[n] = new ArrayList<Object>(); for(Map.Entry<Object, Integer> entry : counts.entrySet()) { byFreq[entry.getValue()].add(entry.getKey()); } for(int n = maxCount; n > 0; n--) { for(Object value : byFreq[n]) { for(int j = 0; j < n; j++) System.out.print(value + " "); } } } public static void main(String [] args) { System.out.print(" input: "); for(int value : args) System.out.print(value + " "); System.out.println(); System.out.print("output: "); printByFreq(args); System.out.println(); } } D:\Personal\java>javac PrintByFreq.java Note: PrintByFreq.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details. D:\Personal\java>java PrintByFreq 2 5 2 8 5 6 8 8 input: 2 5 2 8 5 6 8 8 output: 8 8 8 2 2 5 5 6

A single pass through the array creates a map from value to frequency, then a pass through the map (in insertion order) creates an array by frequency of lists of elements, and finally a pass through the array of lists (in reverse order) prints the values.

--SMQ