Author |
Topic: Array Frequency (Read 1022 times) |
|
johny_cage
Full Member
Gender: 
Posts: 155
|
 |
Array Frequency
« on: Nov 24th, 2007, 5:51am » |
 Quote  Modify
|
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
|
| « Last Edit: Nov 27th, 2007, 12:10pm by johny_cage » |
 IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Array Frequency
« Reply #1 on: Nov 26th, 2007, 10:36am » |
Quote Modify
|
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
|
|
IP Logged |
--SMQ
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print