Rearrange Array - Google Interview

rearrange array

rearrange array，使得相邻两个字符是不一样的。
首先统计所有字符的出现次数，然后每次都拿出现次数最多的那个数字。填进下一个空白的array。
class Node {
char c;
int freq;
public Node(char i, int j) {
this.c = i;
this.freq = j;
}

public void decr() {
freq–;
}
}
public char[] rearrage(char[] arr) {
Map map = new HashMap();
for (char c : arr) {
if (map.contains(c)) {
map.put(c, map.get(c) + 1);
} else {
map.put(c, 1);
}
}
PriorityQueue priority = new PriorityQueue(100, new Comparator(){
@Override
public int compare(Node n1, Node n2) {
return n1.freq.compareTo(n2.freq);
}
});
Iterator iter = map.iterator();
while(iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
priority.add(new Node(entry.getKey(), entry.getValue()));
}

char[] out = new char[arr.length];
int pos = 0;
while(!priority.isEmpty()) {
Node first = priority.remove();
if (pos == 0 || first.c != out[pos-1]) {
out[pos] = first.c;
pos++;
first.decr();
if (first.freq != 0) {
priority.add(first);
}
} else {
Node second = priority.remove();
out[pos] = second.c;
second.decr();
if (second.freq != 0) {
priority.add(second);
}
priority.add(first);
}
}
return out;
}