我在
Java工作.我有一个5个数字的无序列表,范围从0到100,没有重复.我想检测其中3个数字是否是连续的,没有间隙.
例子：
[9,12,13,11,10] true [17,1,2,3,5] true [19,22,23,27,55] false
至于我试过的,还没有.如果我现在写它,我可能会采用最天真的方法来排序数字,然后迭代检查序列是否存在.
解决方法
int sequenceMin(int[] set) {
int[] arr = Arrays.copy(set);
Arrays.sort(arr);
for (int i = 0; i < arr.length - 3 + 1; ++i) {
if (arr[i] == arr[i + 2] - 2) {
return arr[i];
}
}
return -1;
}
这会对数组进行排序,并使用上面的if语句查找所需的序列,并返回第一个值.
没有排序：
(@Pace提到了非排序的愿望.)有限范围可以使用有效的“布尔数组”BitSet.使用nextSetBit的迭代很快.
int[] arr = {9,10};
BitSet numbers = new BitSet(101);
for (int no : arr) {
numbers.set(no);
}
int sequenceCount = 0;
int last = -10;
for (int i = numbers.nextSetBit(0); i >= 0; i = numbers.nextSetBit(i+1)) {
if (sequenceCount == 0 || i - last > 1) {
sequenceCount = 1;
} else {
sequenceCount++;
if (sequenceCount >= 3) {
System.out.println("Sequence start: " + (last - 1));
break;
}
}
last = i;
}
System.out.println("Done");
