f********a
发帖数: 165 | 1 写一个random函数，产生0 ~ n-1的数，但是有一个black list，产生的数不能在black
list里。 bl是sorted的。
int myRandom(int n, vector bl)
{
//.....
}.
时间复杂度log(n)
这里是解
http://www.geeksforgeeks.org/forums/topic/generate-a-random-num
但问题是建立mapping的时候怎么样才能log(n)二分查找 找到下个不在bl里面的数？
follow up是设计一个分布式系统，可以往这个系统里面call一个function叫
getRandom()，每次call返回一个随机数，不能有重复。follow up不用考虑bl. |
j*****4
发帖数: 292 | 2 空间复杂度有要求吗？
【在 f********a 的大作中提到】
: 写一个random函数，产生0 ~ n-1的数，但是有一个black list，产生的数不能在black
: list里。 bl是sorted的。
: int myRandom(int n, vector bl)
: {
: //.....
: }.
: 时间复杂度log(n)
: 这里是解
: http://www.geeksforgeeks.org/forums/topic/generate-a-random-num
: 但问题是建立mapping的时候怎么样才能log(n)二分查找 找到下个不在bl里面的数？
|
w****x
发帖数: 14 | 3 不应该用map，直接产生随机数，然后在black list里走。这时可用二叉树了。
【在 f********a 的大作中提到】
: 写一个random函数，产生0 ~ n-1的数，但是有一个black list，产生的数不能在black
: list里。 bl是sorted的。
: int myRandom(int n, vector bl)
: {
: //.....
: }.
: 时间复杂度log(n)
: 这里是解
: http://www.geeksforgeeks.org/forums/topic/generate-a-random-num
: 但问题是建立mapping的时候怎么样才能log(n)二分查找 找到下个不在bl里面的数？
|
Q********3
发帖数: 143 | 4 假设blacklist里有k个数
1.产生 一个[0,n - k) 的随机数：r=random(0,n - k)
问题就变成了，如何在whitelist里找到对应r这个位置的数,使用binary search
2.find the greatest index a bl[a]<=r
if res = r + a - 1 not in blacklist, return res
else
while( res == bl[a]){
res++;
a++;
}
if res not in blacklist, return res;
有时间写个程序验证一下 |
Q********3
发帖数: 143 | 5 以下程序有bug
int r = myRandom(100,bl);的时候，得到error>0
public class BlacklistRandom {
public static void main(String[] args) {
List bl = new ArrayList();
bl.add(2);
bl.add(4);
bl.add(6);
bl.add(9);
int error = 0;
for(int i=0;i<10000;i++){
int r = myRandom(10,bl);
if(r == 2 ||r == 4 || r == 6 || r == 9){
System.out.println(r);
error ++;
}
}
System.out.println("error count:"+error);
}
private static int myRandom(int n, List bl)
{
int r = new Random().nextInt(n - bl.size() + 1);
int middle = bl.size()/2;
int c = 0;
if(bl.get(middle) == r){
c = middle;
}else if(bl.get(middle) > r){
c = find(r,bl,0,middle);
}else{
c = find(r,bl,middle,bl.size() - 1);
}
if(c>0)
r = r + c - 1;
while(r == bl.get(c)){
r++;
c++;
}
return r;
}
private static int find(int r,List bl,int start,int end){
if(start ==end){
return start;
}else if(end == start +1){
if(r < bl.get(end))
return start;
else return end;
}
int middle = (start + end) /2;
int c = 0;
if(bl.get(middle) == r){
c = middle + 1;
}else if(bl.get(middle) > r){
c = find(r,bl,start,middle);
}else{
c = find(r,bl,middle,end);
}
return c;
}
} |
c******1
发帖数: 37 | 6 black list不知道是不是sort的，如果是直接产生后再list中binary search即可。
follow up可能是找到list中的所有interval，然后分布在不同机器上。 |
n******n
发帖数: 12088 | 7 看不懂你的题目
【在 f********a 的大作中提到】
: 写一个random函数，产生0 ~ n-1的数，但是有一个black list，产生的数不能在black
: list里。 bl是sorted的。
: int myRandom(int n, vector bl)
: {
: //.....
: }.
: 时间复杂度log(n)
: 这里是解
: http://www.geeksforgeeks.org/forums/topic/generate-a-random-num
: 但问题是建立mapping的时候怎么样才能log(n)二分查找 找到下个不在bl里面的数？
|
f********a
发帖数: 165 | 8 bl是sorted的。但是产生n-len(bl)-1的random number后怎么样binary search去除掉
bl里面的数，而得到正确地？
【在 c******1 的大作中提到】
: black list不知道是不是sort的，如果是直接产生后再list中binary search即可。
: follow up可能是找到list中的所有interval，然后分布在不同机器上。
|
f********a
发帖数: 165 | 9 面试官没提。
【在 j*****4 的大作中提到】
: 空间复杂度有要求吗？
|
f********a
发帖数: 165 | 10 怎么用二叉树的？
【在 w****x 的大作中提到】
: 不应该用map，直接产生随机数，然后在black list里走。这时可用二叉树了。
|
|
|
f********a
发帖数: 165 | 11 看不太懂，因为indent不太清楚，大概跑了一下5-->7的例子，r==5不能得到res==7.
【在 Q********3 的大作中提到】
: 假设blacklist里有k个数
: 1.产生 一个[0,n - k) 的随机数：r=random(0,n - k)
: 问题就变成了，如何在whitelist里找到对应r这个位置的数,使用binary search
: 2.find the greatest index a bl[a]<=r
: if res = r + a - 1 not in blacklist, return res
: else
: while( res == bl[a]){
: res++;
: a++;
: }
|
s********x
发帖数: 81 | 12 这是你的面试题吗？还是考古看到的哈。
black list有说明是什么数据结构吗？
linkedlist，array or binary search tree？ |
d**********6
发帖数: 4434 | 13 一用bs就不符合O(n)的要求吧，n个数都要搜一次，就是O(nlog(n))
一旦搜到有重复还得重新生成，生成完又搜一次，worst case会进入死循环的
我觉得mapping才是正道，traverse black list一次，用一个计数器i，每遇到bl中的
元素就跳到下一个，然后把i append到另外一个数组里，就得到map好的数组了
不过map会有问题的，生成的随机数不是平均分布的。你的题目说明不是很清楚，不是
平均分布的随机数有没有问题？
【在 f********a 的大作中提到】
: 怎么用二叉树的？
|
m*****n
发帖数: 2152 | 14 用map，随机数可以做到均匀分布。
我觉得这道题，面试官要的答案就是用map，这一点从follow up就可以看出来。
geek上的解答就是trash，用了就是死。
楼主的function API是自己写的，还是面试官给你？如果是自己写的，这种API一写出
来，就fail一半了。如果是面试官给的，丫就是存心要黑你了。
【在 d**********6 的大作中提到】
: 一用bs就不符合O(n)的要求吧，n个数都要搜一次，就是O(nlog(n))
: 一旦搜到有重复还得重新生成，生成完又搜一次，worst case会进入死循环的
: 我觉得mapping才是正道，traverse black list一次，用一个计数器i，每遇到bl中的
: 元素就跳到下一个，然后把i append到另外一个数组里，就得到map好的数组了
: 不过map会有问题的，生成的随机数不是平均分布的。你的题目说明不是很清楚，不是
: 平均分布的随机数有没有问题？
|
b******i
发帖数: 914 | 15 不懂，为什么说这个API会fail？
int myRandom(int n, vector bl)
{
//.....
}
另外，如果map的话建立map的过程需要O(n)的复杂度，怎么实现O(lgn)?
【在 m*****n 的大作中提到】
: 用map，随机数可以做到均匀分布。
: 我觉得这道题，面试官要的答案就是用map，这一点从follow up就可以看出来。
: geek上的解答就是trash，用了就是死。
: 楼主的function API是自己写的，还是面试官给你？如果是自己写的，这种API一写出
: 来，就fail一半了。如果是面试官给的，丫就是存心要黑你了。
|
w****x
发帖数: 14 | 16 这个题有点费劲，等我调好code，发上来
【在 f********a 的大作中提到】
: 怎么用二叉树的？
|
U***A
发帖数: 849 | 17 是不是可以这样理解题目。
如果需要输出的数产生的概率还是1/n的话，
如果用map的话，随机产生一个数，O(1)查找是不是bl中的数，如果是，那么就接着产
生下一个，要不然就输出。
如果需要输出的数的概率是1/(n-k)的话，
就只能像gfg把所有的数map一对一。然后随机产生（0,n-k)的index，输出index对应的
数就可以了。 |
U***A
发帖数: 849 | 18 是不是可以这样理解题目。
如果需要输出的数产生的概率还是1/n的话，
如果用map的话，随机产生一个数，O(1)查找是不是bl中的数，如果是，那么就接着产
生下一个，要不然就输出。
如果需要输出的数的概率是1/(n-k)的话，
就只能像gfg把所有的数map一对一。然后随机产生（0,n-k)的index，输出index对应的
数就可以了。 |
w****x
发帖数: 14 | 19 下面这个应该是对的，思路是边用二叉树走blacklist，边生成随机数（在leaf上）。
int getnumber(int n, vector& bl) {
if (bl.size() > n) {
cout << " wrong, black list size error! ";
}
int low = 0, high = bl.size() - 1;
int os = 0, oe = n - 1;
double prob, u;
int length1, length2;
while (high > low) {
int mid = (high + low) / 2;
length1 = oe - bl[mid] - (high - mid);
length2 = oe - os - (high - low);
if (length2 > 0)
prob = (double) length1 / length2;
else
prob = 0;
u = rand() / (double) (RAND_MAX + 1);
if (prob <= u) {
//left
high = mid;
oe = bl[mid] - 1;
}
else {
//right
os = bl[mid] + 1;
low = mid + 1;
}
}
length1 = oe - bl[high];
length2 = oe - os;
prob = (double) length1 / length2;
u = rand() / (double) (RAND_MAX + 1);
if (prob <= u) {
int temp = bl[low] - os;
int number = rand() % temp + os;
return number;
}
else {
int temp = oe - bl[high];
int number = rand() % temp + bl[high] + 1;
return number;
}
} |
a***e
发帖数: 413 | 20 这种题会要求现场完整的写出来还是有思路写个大概就行了？感觉把题说明白都花不少
时间吧，45分钟能做3道？ |
|
|
w**5
发帖数: 34 | 21 这样好像可以
public static Random rand = new Random(System.currentTimeMillis());
public static int random(int n, int[] bl)
{
int r = rand.nextInt(n-bl.length);
if (bl.length==0 || r
int offset = r - bl[0] + 1;
int left = 0, right=bl.length-1;
while (left+1 < right) {
int m = (left + right) / 2;
// number of non black list numbers on left
int available_nums = (bl[m] - bl[left]) - (m - left);
if (available_nums < offset) {
offset -= available_nums;
left = m;
} else {
right = m;
}
}
if (offset > (bl[right] - bl[left]) - (right - left)) {
offset++;
}
return bl[left] + offset;
} |
w****x
发帖数: 14 | 22 这个好，想明白了，调试相对很容易。红包收下。
那啥，帅哥，合个影不？
【在 w**5 的大作中提到】
: 这样好像可以
: public static Random rand = new Random(System.currentTimeMillis());
: public static int random(int n, int[] bl)
: {
: int r = rand.nextInt(n-bl.length);
: if (bl.length==0 || r: int offset = r - bl[0] + 1;
: int left = 0, right=bl.length-1;
: while (left+1 < right) {
: int m = (left + right) / 2;
|
U***A
发帖数: 849 | 23 这样能保证0至n-1之间除了bl中的数字都是等概率输出？
1／（n-bl.size())
【在 w**5 的大作中提到】
: 这样好像可以
: public static Random rand = new Random(System.currentTimeMillis());
: public static int random(int n, int[] bl)
: {
: int r = rand.nextInt(n-bl.length);
: if (bl.length==0 || r: int offset = r - bl[0] + 1;
: int left = 0, right=bl.length-1;
: while (left+1 < right) {
: int m = (left + right) / 2;
|
w**5
发帖数: 34 | 24 n = 10, bl --> [4,6,9]
r --> n-bl.size() --> [0, 6]
0 -> 0
1 -> 1
2 -> 2
3 -> 3
4 -> 5
5 -> 7
6 -> 8
数字都是等概率输出 |
f********a
发帖数: 165 | 25 写一个random函数，产生0 ~ n-1的数，但是有一个black list，产生的数不能在black
list里。 bl是sorted的。
int myRandom(int n, vector bl)
{
//.....
}.
时间复杂度log(n)
这里是解
http://www.geeksforgeeks.org/forums/topic/generate-a-random-num
但问题是建立mapping的时候怎么样才能log(n)二分查找 找到下个不在bl里面的数？
follow up是设计一个分布式系统，可以往这个系统里面call一个function叫
getRandom()，每次call返回一个随机数，不能有重复。follow up不用考虑bl. |
j*****4
发帖数: 292 | 26 空间复杂度有要求吗？
【在 f********a 的大作中提到】
: 写一个random函数，产生0 ~ n-1的数，但是有一个black list，产生的数不能在black
: list里。 bl是sorted的。
: int myRandom(int n, vector bl)
: {
: //.....
: }.
: 时间复杂度log(n)
: 这里是解
: http://www.geeksforgeeks.org/forums/topic/generate-a-random-num
: 但问题是建立mapping的时候怎么样才能log(n)二分查找 找到下个不在bl里面的数？
|
w****x
发帖数: 14 | 27 不应该用map，直接产生随机数，然后在black list里走。这时可用二叉树了。
【在 f********a 的大作中提到】
: 写一个random函数，产生0 ~ n-1的数，但是有一个black list，产生的数不能在black
: list里。 bl是sorted的。
: int myRandom(int n, vector bl)
: {
: //.....
: }.
: 时间复杂度log(n)
: 这里是解
: http://www.geeksforgeeks.org/forums/topic/generate-a-random-num
: 但问题是建立mapping的时候怎么样才能log(n)二分查找 找到下个不在bl里面的数？
|
Q********3
发帖数: 143 | 28 假设blacklist里有k个数
1.产生 一个[0,n - k) 的随机数：r=random(0,n - k)
问题就变成了，如何在whitelist里找到对应r这个位置的数,使用binary search
2.find the greatest index a bl[a]<=r
if res = r + a - 1 not in blacklist, return res
else
while( res == bl[a]){
res++;
a++;
}
if res not in blacklist, return res;
有时间写个程序验证一下 |
Q********3
发帖数: 143 | 29 以下程序有bug
int r = myRandom(100,bl);的时候，得到error>0
public class BlacklistRandom {
public static void main(String[] args) {
List bl = new ArrayList();
bl.add(2);
bl.add(4);
bl.add(6);
bl.add(9);
int error = 0;
for(int i=0;i<10000;i++){
int r = myRandom(10,bl);
if(r == 2 ||r == 4 || r == 6 || r == 9){
System.out.println(r);
error ++;
}
}
System.out.println("error count:"+error);
}
private static int myRandom(int n, List bl)
{
int r = new Random().nextInt(n - bl.size() + 1);
int middle = bl.size()/2;
int c = 0;
if(bl.get(middle) == r){
c = middle;
}else if(bl.get(middle) > r){
c = find(r,bl,0,middle);
}else{
c = find(r,bl,middle,bl.size() - 1);
}
if(c>0)
r = r + c - 1;
while(r == bl.get(c)){
r++;
c++;
}
return r;
}
private static int find(int r,List bl,int start,int end){
if(start ==end){
return start;
}else if(end == start +1){
if(r < bl.get(end))
return start;
else return end;
}
int middle = (start + end) /2;
int c = 0;
if(bl.get(middle) == r){
c = middle + 1;
}else if(bl.get(middle) > r){
c = find(r,bl,start,middle);
}else{
c = find(r,bl,middle,end);
}
return c;
}
} |
c******1
发帖数: 37 | 30 black list不知道是不是sort的，如果是直接产生后再list中binary search即可。
follow up可能是找到list中的所有interval，然后分布在不同机器上。 |
|
|
n******n
发帖数: 12088 | 31 看不懂你的题目
【在 f********a 的大作中提到】
: 写一个random函数，产生0 ~ n-1的数，但是有一个black list，产生的数不能在black
: list里。 bl是sorted的。
: int myRandom(int n, vector bl)
: {
: //.....
: }.
: 时间复杂度log(n)
: 这里是解
: http://www.geeksforgeeks.org/forums/topic/generate-a-random-num
: 但问题是建立mapping的时候怎么样才能log(n)二分查找 找到下个不在bl里面的数？
|
f********a
发帖数: 165 | 32 bl是sorted的。但是产生n-len(bl)-1的random number后怎么样binary search去除掉
bl里面的数，而得到正确地？
【在 c******1 的大作中提到】
: black list不知道是不是sort的，如果是直接产生后再list中binary search即可。
: follow up可能是找到list中的所有interval，然后分布在不同机器上。
|
f********a
发帖数: 165 | 33 面试官没提。
【在 j*****4 的大作中提到】
: 空间复杂度有要求吗？
|
f********a
发帖数: 165 | 34 怎么用二叉树的？
【在 w****x 的大作中提到】
: 不应该用map，直接产生随机数，然后在black list里走。这时可用二叉树了。
|
f********a
发帖数: 165 | 35 看不太懂，因为indent不太清楚，大概跑了一下5-->7的例子，r==5不能得到res==7.
【在 Q********3 的大作中提到】
: 假设blacklist里有k个数
: 1.产生 一个[0,n - k) 的随机数：r=random(0,n - k)
: 问题就变成了，如何在whitelist里找到对应r这个位置的数,使用binary search
: 2.find the greatest index a bl[a]<=r
: if res = r + a - 1 not in blacklist, return res
: else
: while( res == bl[a]){
: res++;
: a++;
: }
|
s********x
发帖数: 81 | 36 这是你的面试题吗？还是考古看到的哈。
black list有说明是什么数据结构吗？
linkedlist，array or binary search tree？ |
d**********6
发帖数: 4434 | 37 一用bs就不符合O(n)的要求吧，n个数都要搜一次，就是O(nlog(n))
一旦搜到有重复还得重新生成，生成完又搜一次，worst case会进入死循环的
我觉得mapping才是正道，traverse black list一次，用一个计数器i，每遇到bl中的
元素就跳到下一个，然后把i append到另外一个数组里，就得到map好的数组了
不过map会有问题的，生成的随机数不是平均分布的。你的题目说明不是很清楚，不是
平均分布的随机数有没有问题？
【在 f********a 的大作中提到】
: 怎么用二叉树的？
|
m*****n
发帖数: 2152 | 38 用map，随机数可以做到均匀分布。
我觉得这道题，面试官要的答案就是用map，这一点从follow up就可以看出来。
geek上的解答就是trash，用了就是死。
楼主的function API是自己写的，还是面试官给你？如果是自己写的，这种API一写出
来，就fail一半了。如果是面试官给的，丫就是存心要黑你了。
【在 d**********6 的大作中提到】
: 一用bs就不符合O(n)的要求吧，n个数都要搜一次，就是O(nlog(n))
: 一旦搜到有重复还得重新生成，生成完又搜一次，worst case会进入死循环的
: 我觉得mapping才是正道，traverse black list一次，用一个计数器i，每遇到bl中的
: 元素就跳到下一个，然后把i append到另外一个数组里，就得到map好的数组了
: 不过map会有问题的，生成的随机数不是平均分布的。你的题目说明不是很清楚，不是
: 平均分布的随机数有没有问题？
|
b******i
发帖数: 914 | 39 不懂，为什么说这个API会fail？
int myRandom(int n, vector bl)
{
//.....
}
另外，如果map的话建立map的过程需要O(n)的复杂度，怎么实现O(lgn)?
【在 m*****n 的大作中提到】
: 用map，随机数可以做到均匀分布。
: 我觉得这道题，面试官要的答案就是用map，这一点从follow up就可以看出来。
: geek上的解答就是trash，用了就是死。
: 楼主的function API是自己写的，还是面试官给你？如果是自己写的，这种API一写出
: 来，就fail一半了。如果是面试官给的，丫就是存心要黑你了。
|
w****x
发帖数: 14 | 40 这个题有点费劲，等我调好code，发上来
【在 f********a 的大作中提到】
: 怎么用二叉树的？
|
|
|
U***A
发帖数: 849 | 41 是不是可以这样理解题目。
如果需要输出的数产生的概率还是1/n的话，
如果用map的话，随机产生一个数，O(1)查找是不是bl中的数，如果是，那么就接着产
生下一个，要不然就输出。
如果需要输出的数的概率是1/(n-k)的话，
就只能像gfg把所有的数map一对一。然后随机产生（0,n-k)的index，输出index对应的
数就可以了。 |
U***A
发帖数: 849 | 42 是不是可以这样理解题目。
如果需要输出的数产生的概率还是1/n的话，
如果用map的话，随机产生一个数，O(1)查找是不是bl中的数，如果是，那么就接着产
生下一个，要不然就输出。
如果需要输出的数的概率是1/(n-k)的话，
就只能像gfg把所有的数map一对一。然后随机产生（0,n-k)的index，输出index对应的
数就可以了。 |
w****x
发帖数: 14 | 43 下面这个应该是对的，思路是边用二叉树走blacklist，边生成随机数（在leaf上）。
int getnumber(int n, vector& bl) {
if (bl.size() > n) {
cout << " wrong, black list size error! ";
}
int low = 0, high = bl.size() - 1;
int os = 0, oe = n - 1;
double prob, u;
int length1, length2;
while (high > low) {
int mid = (high + low) / 2;
length1 = oe - bl[mid] - (high - mid);
length2 = oe - os - (high - low);
if (length2 > 0)
prob = (double) length1 / length2;
else
prob = 0;
u = rand() / (double) (RAND_MAX + 1);
if (prob <= u) {
//left
high = mid;
oe = bl[mid] - 1;
}
else {
//right
os = bl[mid] + 1;
low = mid + 1;
}
}
length1 = oe - bl[high];
length2 = oe - os;
prob = (double) length1 / length2;
u = rand() / (double) (RAND_MAX + 1);
if (prob <= u) {
int temp = bl[low] - os;
int number = rand() % temp + os;
return number;
}
else {
int temp = oe - bl[high];
int number = rand() % temp + bl[high] + 1;
return number;
}
} |
a***e
发帖数: 413 | 44 这种题会要求现场完整的写出来还是有思路写个大概就行了？感觉把题说明白都花不少
时间吧，45分钟能做3道？ |
w**5
发帖数: 34 | 45 这样好像可以
public static Random rand = new Random(System.currentTimeMillis());
public static int random(int n, int[] bl)
{
int r = rand.nextInt(n-bl.length);
if (bl.length==0 || r
int offset = r - bl[0] + 1;
int left = 0, right=bl.length-1;
while (left+1 < right) {
int m = (left + right) / 2;
// number of non black list numbers on left
int available_nums = (bl[m] - bl[left]) - (m - left);
if (available_nums < offset) {
offset -= available_nums;
left = m;
} else {
right = m;
}
}
if (offset > (bl[right] - bl[left]) - (right - left)) {
offset++;
}
return bl[left] + offset;
} |
w****x
发帖数: 14 | 46 这个好，想明白了，调试相对很容易。红包收下。
那啥，帅哥，合个影不？
【在 w**5 的大作中提到】
: 这样好像可以
: public static Random rand = new Random(System.currentTimeMillis());
: public static int random(int n, int[] bl)
: {
: int r = rand.nextInt(n-bl.length);
: if (bl.length==0 || r: int offset = r - bl[0] + 1;
: int left = 0, right=bl.length-1;
: while (left+1 < right) {
: int m = (left + right) / 2;
|
U***A
发帖数: 849 | 47 这样能保证0至n-1之间除了bl中的数字都是等概率输出？
1／（n-bl.size())
【在 w**5 的大作中提到】
: 这样好像可以
: public static Random rand = new Random(System.currentTimeMillis());
: public static int random(int n, int[] bl)
: {
: int r = rand.nextInt(n-bl.length);
: if (bl.length==0 || r: int offset = r - bl[0] + 1;
: int left = 0, right=bl.length-1;
: while (left+1 < right) {
: int m = (left + right) / 2;
|
w**5
发帖数: 34 | 48 n = 10, bl --> [4,6,9]
r --> n-bl.size() --> [0, 6]
0 -> 0
1 -> 1
2 -> 2
3 -> 3
4 -> 5
5 -> 7
6 -> 8
数字都是等概率输出 |
c******1
发帖数: 37 | 49 public class RandomBlack {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
RandomBlack fac = new RandomBlack();
List> lss = fac.permu(9);
for(List ls : lss) {
for(int i = 1; i < 10; i++) {
int getRan = fac.getRan(ls, i);
int check = fac.check(ls, i);
if(getRan == check) continue;
else {
System.out.println("ls: " + ls);
System.out.println("i: " + i);
System.out.println("getRan: " + getRan + " chcek: " +
check);
}
}
}
// ArrayList bl = new ArrayList(Arrays.asList(new
Integer[]{1,3}));
// ArrayList bl2 = new ArrayList(Arrays.asList(new
Integer[]{1,3,4,6, 8, 11,12,13, 15, 19, 20, 22, 25}));
// //System.out.println("right: " + random(30, new int[]{1,3,4,6, 8,
11,12,13, 15, 19, 20, 22, 25}));
// System.out.println("6 :"+ getRan(new ArrayList(Arrays.
asList(new Integer[]{1,2,4,5,7})), 2));
// System.out.println("3 :"+ getRan(new ArrayList(Arrays.
asList(new Integer[]{1,2,4})), 1));
// System.out.println("3 :"+ getRan(new ArrayList(Arrays.
asList(new Integer[]{1,2,4,5,6,7})), 1));
// System.out.println("1 :"+ getRan(new ArrayList(Arrays.
asList(new Integer[]{2,3,4,5,6,7,8,9})), 1));
// System.out.println("2 :"+ getRan(new ArrayList(Arrays.
asList(new Integer[]{1,3})), 1));
// System.out.println("4 :"+ getRan(new ArrayList(Arrays.
asList(new Integer[]{1,3})), 2));
}
public List> permu(int n) {
List> out = new ArrayList>();
for(int i = 1; i < n; i++) {
List> tout = new ArrayList>();
for(List ls : out) {
List tls = new ArrayList(ls);
tls.add(i);
tout.add(tls);
}
List tls = new ArrayList();
tls.add(i);
out.add(tls);
out.addAll(tout);
}
return out;
}
public int getRan(List bl, int ranNum) {
int n = bl.size();
if(bl.isEmpty() || ranNum < bl.get(0) ) return ranNum;
if(bl.get(n - 1) - n < ranNum) return ranNum + n;
int s = 0;
int e = n - 1;
while(s + 1 < e) {
int m = (s + e) / 2;
int avi = bl.get(m) - m - 1;
if(m + 1 > e) break;
int aviN = bl.get(m + 1) - m - 2;
if(ranNum > aviN) {
s = m + 1;
}
else if(ranNum <= avi) {
e = m;
}
else {
if(avi == aviN) e = m;
else return ranNum + m + 1;
}
}
//return -1;
return ranNum + s + 1;
}
public int check(List bl, int ranNum) {
for(int i : bl) {
if(ranNum >= i) {
ranNum++;
} else {
break;
}
}
return ranNum;
}
}
有测试代码， 这题其实是在sort array中找最大的小于(target + index)的数，
ranNum相当于一个随机的数。 |
