内容简介：Given two arraysReturn
题目描述：
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 <= 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;
}
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
