870. Advantage Shuffle

TreeMap

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
class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        Arrays.fill(res, -1);

        TreeMap<Integer, Integer> numToCountMap = new TreeMap<>();
        for (int num : nums1) {
            numToCountMap.put(num, numToCountMap.getOrDefault(num, 0) + 1);
        }

        for (int i = 0; i < nums2.length; i++) {
            Map.Entry<Integer, Integer> higherEntry = numToCountMap.higherEntry(nums2[i]);
            if (higherEntry != null) {
                res[i] = higherEntry.getKey();
                maintainNumToCountMap(numToCountMap, higherEntry);
            } else {
                Map.Entry<Integer, Integer> smallestEntry = numToCountMap.higherEntry(-1);
                res[i] = smallestEntry.getKey();
                maintainNumToCountMap(numToCountMap, smallestEntry);
            }
        }

        return res;
    }

    private void maintainNumToCountMap(TreeMap<Integer, Integer> numToCountMap, Map.Entry<Integer, Integer> entry) {
        if (entry.getValue() == 1) {
            numToCountMap.remove(entry.getKey());
        } else {
            numToCountMap.put(entry.getKey(), entry.getValue() - 1);
        }
    }
}

Greedy

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
class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);

        Integer[] numIndex2 = new Integer[nums2.length]; // 存储的为 nums2 值排序后的索引
        for (int i = 0; i < nums2.length; i++) {
            numIndex2[i] = i;
        }

        Arrays.sort(numIndex2, Comparator.comparingInt(o -> nums2[o]));

        int[] res = new int[nums1.length];
        int left = 0, right = nums2.length - 1; // 当前处理的 numIndex2 的下标

        for (int num1 : nums1) {
            // 决定将此 num1 安排至 res 的哪个索引处
            if (num1 > nums2[numIndex2[left]]) {
                res[numIndex2[left++]] = num1;
            } else {
                res[numIndex2[right--]] = num1;
            }
        }

        return res;
    }
}

References

870. Advantage Shuffle