[LeetCode]Advantage Shuffle

题目描述:

LeetCode 870. Advantage Shuffle

Given two arrays A and B of equal size, the advantage of A with respect to B is the number of indices i for which A[i] > B[i].

Return any permutation of A that maximizes its advantage with respect to B.

Example 1:

Input: A = [2,7,11,15], B = [1,10,4,11]
Output: [2,11,7,15]

Example 2:

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

Note:

  1. 1 <= A.length = B.length <= 10000
  2. 0 <= A[i] <= 10^9
  3. 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;
    }
}

 

本文链接:http://bookshadow.com/weblog/2018/07/15/leetcode-advantage-shuffle/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

暂无评论

张贴您的评论