在下面的Java代码中，有没有办法让执行速度更快？
我的Java代码如下所示。
boolean almostIncreasingSequence(int[] sequence) {
Integer[] arr = new Integer[sequence.length];
for(int ctr = 0; ctr < sequence.length; ctr++) {
arr[ctr] = Integer.valueOf(sequence[ctr]); // returns Integer value
}
System.out.println("Integer :: " + arr);
List<Integer> al = new ArrayList<Integer>();
// adding elements of array to arrayList.
Collections.addAll(al, arr);
System.out.println("list :: " + al);
int save, flag = 0;
for(int i=0; i<al.size(); i++) {
save = al.get(i);
al.remove(i);
if(al.size()==1) return true;
for(int j=0; j<al.size()-1; j++) {
if(al.get(j+1) > al.get(j)) {
flag = 0;
continue;
}
else {
flag = 1;
break;
}
}
if(flag == 0) {
return true;
}
al.add(i,save);
}
if(flag == 1)
return false;
return true;
}代码针对的问题是“给定一个整数序列作为一个数组，确定是否可以通过从数组中删除不超过一个元素来获得严格递增的序列。”
对于一些测试用例，它显示执行此命令需要超过3秒。但是，我不确定我可以在哪里进行更改以更快地执行它。我没有访问测试用例的权限。
在这里，我创建了2个for循环，因为在第一个循环中，我生成了一个列表，其中每个索引都将被删除，而在第二个循环中，我将遍历删除了元素的新列表。
例如样本数组是{1,2,4,3}，那么在第一个循环中，我将创建一个数组，它将是{2,4,3}，{1,4,3}，{1,2,3}和{1,2,4}。在第二个循环中，我遍历了所有这4个数组，以比较每个元素。
回答 4
Stack Overflow用户
发布于 2019-01-23 06:30:14
主要的观察结果是列表可以分解为3个部分(可能是空的)：
list = list[0..s) + list[s..e) + list[e..length)其中list[0..s)和list[e..length)是严格递增的列表，而list[s..e)是介于两者之间的东西。
因为您知道这些前缀和后缀列表正在严格地增加，所以您不需要在这些列表中重复检查此属性。
您可以为受约束0 <= s <= e < length约束的s和e选择任何值，但假设您选择它们时，s应尽可能大，e应尽可能小。
如果列表具有所需的总体属性，则：
最大长度为1 (e-s == 1)，并且list[0..s) + list[e..length)也在严格增加。您可以通过比较list[s-1] < list[e].
list[s..e)is empty (s == e)来检查这一点，因此您要求list[0..s-1) + list [e..length)(即删除前缀的最后一个元素)或list[0..s) + list[e+1..length)(即删除后缀的第一个元素)严格递增。检查respectively.
- If
(s == 0 || list[s-1] < list[e])和(e+1 == length || list[s] < list[e+1])list[s..e)有多个元素(e-s > 1)，您需要删除多个元素才能使列表具有所需的属性。
查找s和e的步骤
从整数指针s开始，指针为0。递增它，直到它到达末尾，或者它指向一个元素，使得list[0..s)是一个严格递增的列表，但list[0..s+1)并非如此。
从列表长度处的整数指针e开始。递减它，而e>s和list[e-1..length)不是严格递增的列表。
Stack Overflow用户
发布于 2019-01-23 06:35:35
您的代码包含两个嵌套的for循环，这两个循环都遍历整个列表。这意味着如果你的列表有100000个条目，在最坏的情况下，代码需要100000*100000个步骤。当然，这很慢。
因为列表总是“几乎排序的”，所以您可能不需要检查列表的开头，因为您已经知道它是排序的。直观地说，查看最后几个列表项并记住列表中包含了多少未排序的对就足够了。
Stack Overflow用户
发布于 2019-01-23 06:51:24
更新2:也尝试这个代码(最多2个循环)进一步优化是可能的，但仍然产生O(n)时间
public class TstList {
public static boolean compute(int a[]) {
if (compute_1(a))
return true;
return compute_2(a);
}
public static boolean compute_1(int a[]) {
if (a.length < 2)
return true;
int previous = a[0];
int counter = 0;
for (int i = 1; i < a.length; i++) {
if (previous < a[i]) {
previous = a[i];
continue;
} else {
if (i == 1)
previous = a[i];
else
previous = a[i - 1];
counter++;
}
if (counter > 1)
return false;
}
return true;
}
public static boolean compute_2(int a[]) {
if (a.length < 2)
return true;
int previous = a[0];
int counter = 0;
for (int i = 1; i < a.length; i++) {
if (previous < a[i]) {
previous = a[i];
continue;
} else {
previous = a[i];
counter++;
}
if (counter > 1)
return false;
}
return true;
}
public static void main(String arg[]) {
System.out.println(compute(new int[] { 1, 2, 3, 4, 6 })); \\1
System.out.println(compute(new int[] { 1, 2, 3, 1, 4, 6 })); \\2
System.out.println(compute(new int[] { 1, 2, 1, 3, 1, 4, 6 })); \\3
System.out.println(compute(new int[] { 1, 2, 3, 4, 6, 3 })); \\4
System.out.println(compute(new int[] { 3, 2, 1 })); \\5
System.out.println(compute(new int[] { 10, 1, 2, 3, 4, 5 })); \\6
System.out.println(compute(new int[] { 1, 2, 5, 3, 5 })); \\7
}
}输出
true \\1
true \\2
false \\3
true \\4
false \\5
true \\6
true \\7https://stackoverflow.com/questions/54321133
复制相似问题
腾讯云开发者
