2道算法题的优化过程
最近刷了那么多的算法,感觉自己刚刚有点进步,又被两道简单题搞晕了🙃🙃,彻底暴露了自己对时间复杂度掌握不足的遗漏,因此在这里记录下优化的过程.
¶第一题
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1：
输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。
一看到题目,觉得不难,马上开始写代码,就模拟整个过程,几分钟搞定.
var removeDuplicates = function(nums) {
let len = nums.length
let last = nums[len-1]
let count = 1
for(let i = nums.length-2;i>=0;i--) {
if(nums[i] === last) {
count++
if(count>2) {
len--
for(let j = i;j<len;j++) {
nums[j] = nums[j+1]
}
}
}else {
count = 1
last = nums[i]
}
}
return len
};
刚好这几天几个同事都在打卡每日一题,我们交流了一下,我把自己的代码给同事看了看,一个同事立马说,你这个时间复杂度太高了,我仔细看了看代码,确实,循环里面移动数组,大概复杂度O(n^2).
听了同事的的解法,我顿悟了,原来双指针就好了,快慢指针,慢指针保持长度,快指针每次+1用来检查后面的元素,遇到不同的元素,并且前方已经出现了两个重复的,就覆盖前方慢指针的元素,然后慢指针继续+1
下面是代码:
var removeDuplicates = function(nums) {
let n = nums.length
if(n<2) {
return n
}
let slow = 2
let fast = 2
while(fast<n) {
if(nums[slow-2] !== nums[fast]) {
nums[slow] = nums[fast]
slow++
}
fast++
}
return slow
};
这样时间复杂度就被优化到了O(n),只遍历了一边.
经过自己的测试,在长度为999999,三个一组相同的数组的运行测试下,第二种花费大概3ms,而第一种,居然用了100000+ms,相差了3万倍!!!🤯 🤯 🤯 🤯 🤯
¶第二题
小力将 N 个零件的报价存于数组 nums。小力预算为 target，假定小力仅购买两个零件，要求购买零件的花费不超过预算，请问他有多少种采购方案。
注意：答案需要以 1e9 + 7 (1000000007) 为底取模，如：计算初始结果为：1000000008，请返回 1
示例 1：
输入：nums = [2,5,3,5], target = 6
输出：1
解释：预算内仅能购买 nums[0] 与 nums[2]。
示例 2：
输入：nums = [2,2,1,9], target = 10
输出：4
解释：符合预算的采购方案如下：
nums[0] + nums[1] = 4
nums[0] + nums[2] = 3
nums[1] + nums[2] = 3
nums[2] + nums[3] = 10
第一眼看到这个题,心想这么简单的吗?
立马又是双层循环遍历一边,果不其然超时了,一看给的测试用例,长度 2 <= nums.length <= 10^5
考虑到没有负数,于是加了个判断第一个数的长度是否大于target,然而还是超时.
想了想,先排下顺序吧,然后二分找到小于target的部分,在这个范围内判断,后来又想,如果target很大怎么办?不还是要遍历很多次吗?
想啊想,死掉n个脑细胞,m根头发后,我明白了,在一个顺序的数组里,如果下标i和下标j满足小于target,那么i和其他小于j的其他组合都满足,这个个数是(j-i)个,然后i++继续判断就行了,如果大于target了,就大数的下标,j 向左移动j-- 就行了. 想明白后,才发现已经过去1个小时了.马上动手写代码
var purchasePlans = function(nums, target) {
const MOD = 1000000007
nums.sort((a,b) => a-b)
let i = 0
let j = nums.length-1
let res = 0
while(i<j) {
if(nums[i] + nums[j] <= target) {
res+=j-i
res = res%MOD
i++
}else {
j--
}
}
return res
};
这样就O(n)了,同时,不要忘了模MOD.
注意时间复杂度,不要再写低效率的代码了💪💪💪💪💪