Distant Barcodes
给一个数组, 求返回一个数组, 里面的相邻数字不相同. 这个先统计一下频率, 然后插孔间隔放置.
class Solution {
public int[] rearrangeBarcodes(int[] nums) {
Map<Integer, Integer> count = new HashMap<>();
for(int n : nums)
count.put(n, count.getOrDefault(n, 0) + 1);
PriorityQueue<Map.Entry<Integer,Integer>> q = new PriorityQueue<Map.Entry<Integer,Integer>>(new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
if (o2.getValue() != o1.getValue())
return o2.getValue() - o1.getValue();
else
return o1.getKey() - o2.getKey();
}
});
for(Map.Entry<Integer, Integer> e : count.entrySet())
q.add(e);
int i = 0;
int[] res = new int[nums.length];
Map.Entry<Integer, Integer> e;
while(!q.isEmpty()) {
e = q.poll();
int j = 0;
int total = e.getValue();
while(j < total) {
if(res[i] == 0) { // pull it
res[i] = e.getKey();
i += 2;
j++;
}
else {//skip it
i++;
}
if(i >= nums.length)
i = 0;
}
}
return res;
}
}