Address: leetcode-cn.com/problems/ra…
Topic Description:
Given a blacklist containing a non-repeating integer in [0, n), write a function that returns a random integer from [0, n) that is not in the blacklist.
Optimize it so that it makes fewer calls to the system method math.random ().
Tip:
1 <= n <= 1000000000 0 <= blacklist.length < min(100000, n) [0, n) Does not contain N, see interval notation for details. Example 1:
Input: [” Solution “, “pick”, “pick”, “pick”] [[1, []], [], [], []] output: [null, 0, 0] example 2:
Input: [” Solution “, “pick”, “pick”, “pick”] [[2, []], [], [], []] output: [null, 1,1,1] example 3:
Input: [” Solution “, “pick”, “pick”, “pick”] [[3, [1]], [], [], []] output: [null, zero,0,2] example 4:
Input: [” Solution “, “pick”, “pick”, “pick”] [[4, [2]], [], [], []] output: [null, 1,3,1] input syntax description:
The input is two lists: the name of the calling member function and the arguments to the call. The constructor of Solution takes two arguments, n and a blacklist. Pick has no arguments. The input argument is a list. Even if the argument is empty, an empty list [] is entered
A.
The meaning of the title is very clear, but it is difficult to understand when looking at the example: here is a brief explanation.
Input: [” Solution “, “pick”, “pick”, “pick”] [[4, [2]], [], [], []] output: [null, 1,3,1] : mean will pick three times a Solution constructor function called; The Solution constructor is called with length 4, [2]; No arguments are passed when you call pick.
Three official methods of solving the problem
To be honest, when I got the problem, I could only think of the first way to do it. I don’t know if you could think of any of those.
Solution 1: Maintain a whitelist
If we have a whitelist (that is, all integers other than the blacklist), then we can randomly select integers from the whitelist and return them.
We get the whitelist by first putting all the integers in [0, N) into the set, then removing all the numbers that have appeared in the blacklist and putting the remaining numbers into the list.
Leetcode Official code:
class Solution {
List<Integer> w;
Random r;
public Solution(int n, int[] b) {
w = new ArrayList<>();
r = new Random();
Set<Integer> W = new HashSet<>();
// Now add all data to the whitelist
for (int i = 0; i < n; i++) W.add(i);
// Remove the number from the blacklist
for (int x : b) W.remove(x);
// Build a true whitelist
w.addAll(W);
}
public int pick(a) {
returnw.get(r.nextInt(w.size())); }}Copy the codeSolution method 2: binary search method
Official explanation:
Question:
- Why mid = (lo + Hi + 1) / 2 instead of mid = (lo + Hi) / 2
- C = B[mid] -mid indicates the number of whitelists that can be inserted before the blacklist in the general list (the general list can be interpreted as a list of [0,n])
- Why does the dichotomy search end with an official phenomenon
So with that in mind let’s try to write binary search ourselves.
C = B[mid] -mid = c [mid] -mid = c [mid] -mid = c [mid] -mid = c [mid] -mid = c [mid] -mid = c [mid] -mid = c [mid] -mid = c [mid] -mid = c If 2-1 = 1, you can insert one whitelist before B[1]
We know that the end of binary search is lo==hi at this position, so how do we determine whether the KTH whitelist is to the left or right of B[lo] on the total list?
The calculation method of the KTH whitelist data
1. If possible, K falls to the left of the blacklist. In special cases, the maximum number of the blacklist is smaller than the KTH whitelist
Note that the following may not be easy to understand: Before the h blacklist can insert the total number of whitelist preCountW, in the total list of the h blacklist number on the left of the first is the first preCountW -1 whitelist number, then the k whitelist is the h blacklist value – (preCountW – k); In a special case then the KTH whitelist = the value of the h blacklist + k-precountw
The code is as follows:
/** ** k falls to the left of H in the general list ** /
private int pick2fenLeft(int k) {
System.out.println("pick2fen start "+k);
if (blacklistLength == 0) {
return k;
}
int l = 0, h = blacklist.length - 1;
while(l ! = h) {int mid = (l + h) / 2;
// Blacklist [mid]-mid Indicates the data in the current blacklist - Blacklist order = The number of whitelist that can be inserted before the current position
int preCountW = blacklist[mid] - mid;
if (preCountW >= k+1) {// The KTH mid actually contains k+1
h = mid;// In this case, there must be K +1 whitelist before blacklist[mid], but the condition of blacklist[mid-1] cannot be determined, so h cannot be reduced
} else {
l = mid+1;// Put it on the left side}}int preCountW = blacklist[h] - h;
System.out.println("pick2fen end l = " + l + " h= " + h+" preCountW ="+preCountW +" k = "+k);
if (preCountW >= k+1) {// It falls on the left
// The total number of whitelists before h
// preCountW -(k+1) is the distance between the current position and the KTH blank element. The coordinates of k start at 0
// the interval from the KTH to the first precountw-1 is precountw-1 -k; The total spacing is precountw-k;
// blacklist[h] - preCountW +k =h + preCountW - preCountW + k
return h+k;
} else {
//h + preCountW + (k - preCountW)
return h+k+1; }}Copy the code2. If possible, K falls to the right of the blacklist. In special cases, the minimum number of the blacklist is larger than that of the KTH whitelist
/** ** k falls to the right of H ** / on the general list
private int pick2fen(int k) {
System.out.println("pick2fen start "+k);
if (blacklistLength == 0) {
return k;
}
int l = 0, h = blacklist.length - 1;
while(l ! = h) {int mid = (l + h+1) / 2;
// Blacklist [mid]-mid Indicates the data in the current blacklist - Blacklist order = The number of whitelist that can be inserted before the current position
try {
int preCountW = blacklist[mid] - mid;
if (preCountW >= k+1) {// In fact, the KTH mid contains k+1. In this case, k is on the left of the blacklist mid
h = mid-1;// Put it on the right
} else{ l = mid; }}catch (Exception r){
System.out.println("mid is "+mid);
throwr; }}int preCountW = blacklist[h] - h;
System.out.println("pick2fen end l = " + l + " h= " + h+" preCountW ="+preCountW +" k = "+k);
if (preCountW >= k+1) {//preCountW >= k+1 is guaranteed to fall to the left of the h blacklist number
// The first whitelist on the left of the blacklist is the first whitelist. Its value is = blacklist[h]-1
Blacklist [h]-1 - (precountw-1-k) = h + precountw-1-precountw + 1 + k = h + k; blacklist[h]-1 - (precountw-1-k) = h + precountw-1-precountw + 1 + k = h + k;
return k+h;// In this case, h = 0
} else {// In this case, the maximum number of blacklists is smaller than that of whitelists. So the KTH whitelist = the total number of blacklists +k +1 (since k and the total number of blacklists h both start at 0, so add 1)
return h+k+1; }}Copy the codeYou can see that the final return value is the same whether we select k to the left or right of the blacklist by default.
**l=mid+1 **l=mid+1 When h = mid-1, k falls to the right of the blacklist. But in these two cases, the starting method of MID is different. They are not interchangeable.
Method 3: Blacklist mapping
Compared with binary search, blacklist mapping is very simple: the total length is n, the whitelist length is WL, the blacklist length is BL; wl + bl = n; We can have the following conclusion: in the total list of the top wl number m blacklist number (m<=wl) then in [wl,n] there must be m whitelist number
Leetcode Official code:
class Solution {
Map<Integer, Integer> m;
Random r;
int wlen;
public Solution(int n, int[] b) {
m = new HashMap<>();
r = new Random();
wlen = n - b.length;
Set<Integer> w = new HashSet<>();
// Note that it starts with wlen
for (int i = wlen; i < n; i++) w.add(i);
for (int x : b) w.remove(x);
Iterator<Integer> wi = w.iterator();
for (int x : b)
if (x < wlen)
m.put(x, wi.next());
}
public int pick(a) {
int k = r.nextInt(wlen);
returnm.getOrDefault(k, k); }}Copy the codeCode reference address: github.com/xiaolutang/…