50-优势洗牌-贪心算法

题目链接

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        // 1. 对两个数组进行排序,但是nums2数组需要保留原样
         Arrays.sort(nums1);
        int[] sortB = nums2.clone();
        Arrays.sort(sortB);
        // 保存对应的最大化的下标值
        Map<Integer, Deque<Integer>> map = new HashMap<>();
        Deque<Integer> aq = new LinkedList<>();
        for(int b : sortB) {
            map.put(b, new LinkedList<>());
        }
        int i = 0;
        for(int a : nums1) {
            if(a > sortB[i]) {
                map.get(sortB[i++]).offer(a);
            } else {
                aq.offer(a);
            }
        }
        int[] ans = new int[nums2.length];
        // 处理B中对应的优势最大化的下标
        for(int j = 0; j < nums2.length; j++) {
            Deque<Integer> d = map.get(nums2[j]);
            if(d.size() == 0) {
                ans[j] = aq.removeLast();
            } else {
                ans[j] = d.removeLast();
            }
        }
        return ans;
    }
}