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相当于一个随机的数。
