LeetCode解析

LeetCode解析

题目：

给定一个包含 [0，n ) 中独特的整数的黑名单 B，写一个函数从 [ 0，n ) 中返回一个不在 B 中的随机整数。
对它进行优化使其尽量少调用系统方法 Math.random() 。

提示:

1.1 <= N <= 1000000000
2.0 <= B.length < min(100000, N)
3.[0, N) 不包含 N，详细参见 interval notation 。

示例1：

输入: [“Solution”,“pick”,“pick”,“pick”] [[1,[]],[],[],[]]
输出:[null,0,0,0]

示例2：

输入: [“Solution”,“pick”,“pick”,“pick”] [[2,[]],[],[],[]]
输出: [null,1,1,1]

示例3：

输入: [“Solution”,“pick”,“pick”,“pick”] [[3,[1]],[],[],[]]
输出: [null,0,0,2]

示例4：

输入: [“Solution”,“pick”,“pick”,“pick”] [[4,[2]],[],[],[]]
输出:[null,1,3,1]

简单介绍：
题目：黑名单中的随机数
题目难度：困难
使用语言：JAVA。
这道题来自leetcode题库的排序标签。
数据结构的排序算法有许多，其中比较常见的是冒泡、选择、堆、快速等排序方法

解题思路：
首先看题、分析题意，我们可以明确1个关键点：
1.如何利用黑名单得到我们想要的白名单
既然，我们已经分析出来题目的关键任务了，下面我们就可以开始思考实现了。
我们采用算法与数据结构的思路来剖析一下这题，

数据结构：
要实现对数据的操作，我们要先明确存储数据的数据结构。
该题的数据结构的作用，是保存黑名单。
我们采用了1个int型的数组来存储我们的黑名单

算法：
既然明确了int型数组作为解决该题的数据结构，我们就可以开始我们的算法分析了。
1.初始化，对黑名单进行排序，将排序好的黑名单存储起来
2.获取白名单的第k个数w[k]，二分查找。
如果黑名单中最小的数b[low]都大于k，则w[k]=k。
否则，w[k]>b[low]，则w[k]=k+low+1

代码部分：

import java.util.*;public class Solution {int n;int[] b;Random r;public Solution(int N, int[] blacklist) {n=N;Arrays.sort(blacklist);//黑名单排序//System.arraycopy(blacklist,0,b,0,blacklist.length);b=blacklist;//将b指向blacklist数组r=new Random();}public int pick() {int k&#Int(n-b.length);//白名单中第k个数int low=0;//二分法起点int high=b.length-1;//二分法顶点while(low<high) {int mid=(low+high+1)/2;if(b[mid]-mid>k) {//比b[mid]小的白名单数大于k，说明k在b[mid]之前high=mid-1;}else low=mid;//k在b[mid]之后}if(low==high&&b[low]-low<=k) {//b[low]<w[k]return k+low+1;}else return k;//b[low]>w[k]||low!=high}
}

结语：
晚安！晚安！晚安！晚安！晚安！晚安！晚安！晚安！晚安！晚安！