-
Notifications
You must be signed in to change notification settings - Fork 2
/
Advantage Shuffle.java
48 lines (38 loc) · 1.24 KB
/
Advantage Shuffle.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
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
*/
class Solution {
public int[] advantageCount(int[] A, int[] B) {
if (A == null || B == null || A.length != B.length) {
return new int[0];
}
TreeMap<Integer, Integer> treeMap = new TreeMap<>();
for (int num : A) {
treeMap.put(num, treeMap.getOrDefault(num, 0) + 1);
}
int[] result = new int[A.length];
for (int i = 0; i < A.length; i++) {
Integer candidate = treeMap.higherKey(B[i]);
if (candidate == null) {
candidate = treeMap.firstKey();
}
treeMap.put(candidate, treeMap.get(candidate) - 1);
if (treeMap.get(candidate) == 0) {
treeMap.remove(candidate);
}
result[i] = candidate;
}
return result;
}
}