Distant Barcodes
给一个数组, 求返回一个数组, 里面的相邻数字不相同. 这个先统计一下频率, 然后插孔间隔放置.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
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; } } |