minDistance

题目：输出任意permutation使得List中的相同element的间距要>=minDistance

例1：
输入：[B, E, A, C, D, F, F]，2  
输出：[B, F, A, C, D, E, F]  (两个F之间的间距为4大于2)

例2：
输入：[A, B, B]，1 
输出：[A, B, B]  (两个B之间的间距为1)

例3：
输入：[A, B, B]，2  
输出：[B, A, B]  (两个B之间的间距为2)

解题思路：
和Rerrange String的思路比较像
先按频率排序，然后每次取出频率最高的d个不同的放到result，然后把剩下的再排序，再放。。。。
一开始A3 B3 C1 D1 E1   (A3代表3个A)
找最大的三个：ABC
之后A2 B2 D1 E1
最大的三个加入：ABCABD
之后A1 B1 E1
ABCABDABE

public class Solution {
  public char[] getMinDistance(char[] chars, int minDistance) {
    HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    for(int i=0; i<chars.length; i++) {
      char c = chars[i];
      if(map.containsKey(c)) {
        map.put(c, map.get(c)+1);
      } else {
        map.put(c, 1);
      }
    }
    
    PriorityQueue<Element> maxHeap = new PriorityQueue<Element>(1, new Comparator<Element>() {
      public int compare(Element e1, Element e2) {
        return e2.count - e1.count;
      }
    });
    
    for(char c : map.keySet()) {
      int count = map.get(c);
      Element e = new Element(c, count);
      maxHeap.offer(e);
    }
    
    int index = 0;
    char[] result = new char[chars.length];
    
    while(!maxHeap.isEmpty()) {
      Queue<Element> queue = new LinkedList<Element>();
      int i=0;
      for(; i<minDistance && !maxHeap.isEmpty(); i++) {
        queue.offer(maxHeap.poll());
      }
      if(i < minDistance && queue.peek().count > 1) {   // 说明不可能有这样的char组合满足minDistance
        return new char[0];                    // queue.peek().count > 1 说明heap里还有剩余，则不可能满足minDistance要求，如果没有剩余则可以满足
      }
      while(!queue.isEmpty()) {
        Element e = queue.poll();
        result[index++] = e.c;
        e.count --;
        if(e.count > 0) {
          maxHeap.offer(e);
        }
      }
    }
    return result;
  }
}

class Element {
  char c;
  int count;
  public Element(char c, int count) {
    this.c = c;
    this.count = count;
  }
}