所以我必须编写一个满足以下要求的函数:
Given a sequence of integers as an array, determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.
Example:
For sequence = [1, 3, 2, 1], the output should be
almostIncreasingSequence(sequence) = false;
There is no one element in this array that can be removed in order to get a strictly increasing sequence.
For sequence = [1, 3, 2], the output should be
almostIncreasingSequence(sequence) = true.
You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].
Input/Output
[time limit] 4000ms (js)
[input] array.integer sequence
Guaranteed constraints:
2 ≤ sequence.length ≤ 105,
-105 ≤ sequence[i] ≤ 105.
所以除了一个问题,我的代码可以正常工作——它必须通过 30 次测试,时间限制为 4000 毫秒,但每次都会在第 30 次测试时超时。我曾尝试修改它以使其运行得更快,但每次我这样做时它都无法正常工作。尽管从技术上讲我只需要编写一个函数,但我将其分解为三个独立的函数。这是我的代码:
var greater = function(a, b) {
if (a < b) {
return true
} else {
return false
}
}
function greaterThan(arr) {
for (var i = 0; i < arr.length-1; i++) {
var curr = arr[i]
var next = arr[i + 1]
if (greater(curr, next) === false) {
return false
}
}
return true
}
function almostIncreasingSequence(sequence) {
for(var i = 0; i < sequence.length; i++) {
var newArr = sequence.slice()
newArr.splice(i, 1)
if (greaterThan(newArr) === true) {
return true
}
}
return false
}
那么如何在不使用两个 for 循环/迭代的情况下让它运行得更快呢?
最佳答案
改进算法可能比改进代码带来更好的结果。问题是:
如果序列在索引
i
处不是严格递增的, 这样a[i]>=a[i+1]
是真的,或者a[i]
或a[i+1]
必须移除以使数组严格递增 - 它们不能都留在原地。如果输入数组可以通过只删除一个元素来固定,并且它在
i
之后递减第 th 个元素,它必须通过删除带有下标i
的元素而严格增加或(i+1)
.
比较返回前检查原数组和至多两个子数组的效率true
或 false
, 检查与原始数组长度相同的数组数。我会把重写代码留给你——这不是我的作业:-)
关于javascript:如何使函数运行得更快,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44915577/