-
Notifications
You must be signed in to change notification settings - Fork 2
/
AdvantageShuffle.java
45 lines (40 loc) · 1.26 KB
/
AdvantageShuffle.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
package src.java.medium.array;
import java.util.Arrays;
public class AdvantageShuffle {
// Find the closest larger number from A respect to the number from B
public int[] advantageCount(int[] A, int[] B) {
int[] ret = new int[A.length];
Arrays.fill(ret, -1);
boolean[] used = new boolean[A.length];
Arrays.sort(A);
for (int i=0; i<B.length; i++) {
int index = search(A, B[i]);
while (index<A.length && (used[index] || A[index]<=B[i]))
index++;
if (index<A.length) {
ret[i] = A[index];
used[index] = true;
}
}
int j = 0;
for (int i=0; i<ret.length; i++) {
if (ret[i] == -1) {
while (j < A.length && used[j])
j++;
ret[i] = A[j];
used[j] = true;
}
}
return ret;
}
private int search(int[] A, int t) {
int start = 0, end = A.length-1;
while(start < end) {
int mid = start + (end-start)/2;
if (A[mid] == t) return mid;
else if (A[mid] > t) end = mid-1;
else start = mid+1;
}
return start;
}
}