我想回答以下问题:给定一个有序数字和一些非序列数字的有序数组,写一个算法,获得每个连续组的一对{开始,结束}数字。连续数字只有1的差异。连续数字的数组 - 算法
到目前为止,我能想到的只有蛮力的方法:
public static void main(String[] args) {
int[] array = { 4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27 };
Map<Integer, Integer> list = new HashMap<Integer, Integer>();
list = findIndex(array);
}
// Bruteforce
private static Map<Integer, Integer> findIndex(int[] array) {
Map<Integer, Integer> list = new HashMap<Integer, Integer>();
int x = -1, y = -1;
int end = array.length;
for (int i = 0; i < end; i++) {
x = i;
while (i < end - 1) {
if (array[i] + 1 == array[i + 1]) {
i++;
y = i;
} else {
if (x != y && x >= 0) {
list.put(x, y);
System.out.println("i = " + x + " to j = " + y);
i = i + 1;
break;
}
}
}
}
return list;
}
输出:
i = 0 to j = 5
i = 7 to j = 10
i = 12 to j = 14
它工作正常,但如何提高时间复杂度?
的与您的代码问题不是算法的复杂性,而是清晰度。这段代码实际上只是在数组中迭代一次,尽管嵌套循环隐藏了这一点。 O(n)是你能做的最好的。 –
@AndrewPalmer我们不能在这里使用二分搜索? – Sarah
我不得不说这是一个非常有趣的想法。它绝对不会是二分搜索的标准应用程序,但根据有关阵列的保证,您可以确定有8个缺口,并开始缩小差距。 –