[LeetCode]Advantage Shuffle

Example 2:

Input: A = [12,24,8,32], B = [13,25,32,11]
Output: [24,32,8,12]

Note:

1 <= A.length = B.length <= 10000
0 <= A[i] <= 10^9
0 <= B[i] <= 10^9

题目大意：

给定两个等长数组A和B。求A的排列，使得满足条件A[i] > B[i]的下标最多。

解题思路：

贪心（Greedy Algorithm）

利用数组B，构造TreeMap<Integer, List<Integer>，其中key为B的元素，value为其下标（由于可能存在重复的元素，因此用列表）

遍历数组A的元素a：

  在B中取出大于a的最小元素对应的任意下标；若不存在大于a的元素，则取出当前B中的最大元素对应的下标，记为idx；

  将a放在idx处

Java代码：

class Solution {
    public int[] advantageCount(int[] A, int[] B) {
        int size = A.length;
        TreeMap<Integer, LinkedList<Integer>> mapB = new TreeMap<>();
        for (int i = 0; i < size; i++) {
            LinkedList<Integer> idxList = 
                    mapB.getOrDefault(B[i], new LinkedList<>());
            idxList.add(i);
            mapB.putIfAbsent(B[i], idxList);
        }
        int[] ans = new int[size];
        for (int i = 0; i < size; i++) {
            Integer key = mapB.lowerKey(A[i]);
            if (key == null) {
                key = mapB.lastKey();
            }
            LinkedList<Integer> idxList = mapB.get(key);
            int index = idxList.removeLast();
            ans[index] = A[i];
            if (idxList.isEmpty()) {
                mapB.remove(key);
            }
        }
        return ans;
    }
}