内容简介：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;
}
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Building Websites with Joomla!
H Graf / Packt Publishing / 2006-01-20 / USD 44.99
This book is a fast paced tutorial to creating a website using Joomla!. If you've never used Joomla!, or even any web content management system before, then this book will walk you through each step i......一起来看看 《Building Websites with Joomla!》 这本书的介绍吧!
