https://leetcode.com/problems/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]
https://leetcode.com/problems/advantage-shuffle/discuss/149840/C%2B%2BJava-Greedy-Solution-Using-Map
Count elements in
For each element in
Otherwise, we'll take the smallest element.
Then we update the
A to a map m.For each element in
B, find the least bigger element in map m.Otherwise, we'll take the smallest element.
Then we update the
m.
Idea is that we need a sorted structure that makes it easy to find a smallest number higher than B[i]. If no such number exists, you use your smallest number from A at that position to maximize our chances to find better positions later.
public int[] advantageCount(int[] A, int[] B) {
TreeMap<Integer, Integer> map = new TreeMap<>();
//Add each number to the map along with count
for (int a : A) map.put(a, map.getOrDefault(a, 0)+1);
int[] ret = new int[A.length];
for (int i = 0; i < B.length; i++) {
//Find the best number to beat B[i]
ret[i] = findBestMatch(B[i], map);
}
return ret;
}
private int findBestMatch(int target, TreeMap<Integer, Integer> map) {
// See if there exists a number higher than the target
Integer res = map.higherKey(target);
// If a number higher than target does not exist, use the smalles available number
if (res == null) res = map.firstKey();
//Update the TreeMap, remove the key if the number has 0 remaining occurences
map.put(res, map.get(res) - 1);
if (map.get(res) == 0) map.remove(res);
return res;
}https://leetcode.com/problems/advantage-shuffle/discuss/154417/Simple-Java-Solution-with-the-idea-of
运用田忌赛马的思路，如果A中有相应的higher元素，使用最小的higher元素。否则使用A中最小的元素 :)
public int[] advantageCount(int[] A, int[] B) {
// the tree map stores <value, count> pairs of array A
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int num: A) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
// for each value in B, get the A entry with smallest higher key or the smallest key if not exist
int[] res = new int[A.length];
for (int i = 0; i < B.length; i++) {
Map.Entry<Integer, Integer> matchingEntry = map.higherEntry(B[i]);
if (matchingEntry == null) {
matchingEntry = map.firstEntry();
}
res[i] = matchingEntry.getKey();
if (matchingEntry.getValue() == 1) {
map.remove(matchingEntry.getKey());
} else {
map.put(matchingEntry.getKey(), matchingEntry.getValue() - 1);
}
}
return res;
}
If the smallest card
a in A beats the smallest card b in B, we should pair them. Otherwise, a is useless for our score, as it can't beat any cards.
Why should we pair
a and b if a > b? Because every card in A is larger than b, any card we place in front of b will score a point. We might as well use the weakest card to pair with b as it makes the rest of the cards in A strictly larger, and thus have more potential to score points.
Algorithm
We can use the above intuition to create a greedy approach. The current smallest card to beat in
B will always be b = sortedB[j]. For each card a in sortedA, we will either have a beat that card b (put a into assigned[b]), or throw a out (put a into remaining).
Afterwards, we can use our annotations
assigned and remaining to reconstruct the answer. Please see the comments for more details.
public int[] advantageCount(int[] A, int[] B) {
int[] sortedA = A.clone();
Arrays.sort(sortedA);
int[] sortedB = B.clone();
Arrays.sort(sortedB);
// assigned[b] = list of a that are assigned to beat b
Map<Integer, Deque<Integer>> assigned = new HashMap();
for (int b : B)
assigned.put(b, new LinkedList());
// remaining = list of a that are not assigned to any b
Deque<Integer> remaining = new LinkedList();
// populate (assigned, remaining) appropriately
// sortedB[j] is always the smallest unassigned element in B
int j = 0;
for (int a : sortedA) {
if (a > sortedB[j]) {
assigned.get(sortedB[j++]).add(a);
} else {
remaining.add(a);
}
}
// Reconstruct the answer from annotations (assigned, remaining)
int[] ans = new int[B.length];
for (int i = 0; i < B.length; ++i) {
// if there is some a assigned to b...
if (assigned.get(B[i]).size() > 0)
ans[i] = assigned.get(B[i]).pop();
else
ans[i] = remaining.pop();
}
return ans;
}
X. PQ
public int[] advantageCount(int[] A, int[] B) {
Arrays.sort(A);
int n=A.length;
int[] res= new int[n];
PriorityQueue<int[]> pq= new PriorityQueue<>((a,b)->b[0]-a[0]);
for (int i=0; i<n; i++) pq.add(new int[]{B[i], i});
int lo=0, hi=n-1;
while(!pq.isEmpty()){
int[] cur= pq.poll();
int idx=cur[1], val=cur[0];
if (A[hi]>val) res[idx]=A[hi--];
else res[idx]=A[lo++];
}
return res;
} public int[] advantageCount(int[] A, int[] B) {
Arrays.sort(A);
int n=A.length;
int[] res= new int[n];
PriorityQueue<int[]> pq= new PriorityQueue<>(new Comparator<int[]>(){
public int compare(int[] a, int[] b){
return b[0]-a[0];
}
});
for (int i=0; i<n; i++) pq.add(new int[]{B[i], i});
int lo=0, hi=n-1;
while(!pq.isEmpty()){
int[] cur= pq.poll();
int idx=cur[1], val=cur[0];
if (A[hi]>val) res[idx]=A[hi--];
else res[idx]=A[lo++];
}
return res;
}
