leetcode每天5题-Day37
目录
- 1.合并区间
- 2.插入区间
- 3.最小路径和
- 4.超级丑数
- 5.数组中重复的数据
1.合并区间
56. 合并区间-中等
按区间左端点排序
var merge = function(intervals) {
// 按区间的左端点排序
intervals.sort((a,b)=>a[0]-b[0]);
const ans=[];
for(let i=0;i<intervals.length;i++){
let l=intervals[i][0],r=intervals[i][1];
// 区间段中的区间左端点大于ans中右端点
if(ans.length==0||l>ans[ans.length-1][1]){
ans.push([l,r]);
}else{
// 更新ans中右端点的值
ans[ans.length-1][1]=Math.max(ans[ans.length-1][1],r);
}
}
return ans;
};
时间复杂度：O(nlogn)，其中n为区间的数量。除去排序的开销，我们只需要一次线性扫描，所以主要的时间开销是排序的O(nlogn)。
空间复杂度：O(logn)，其中n为区间的数量。这里计算的是存储答案之外，使用的额外空间。O(logn)即为排序所需要的空间复杂度。
2.插入区间
57. 插入区间-中等
3.最小路径和
64. 最小路径和-中等
4.超级丑数
313. 超级丑数-中等
5.数组中重复的数据
442. 数组中重复的数据-中等
做出来这道题并不难，但题目要求：设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。
①哈希
var findDuplicates = function(nums) {
const map = new Map();
for(const num of nums){
map.set(num,(map.get(num) || 0) + 1);
}
const set=new Set();
for(const [k,v] of map.entries()){
if(v===2) set.add(k);
}
let ans=Array.from(set);
return ans;
};
空间复杂度是O(n)，不符合题目要求的常数空间。所以我们应该原地修改数组。
②将元素交换到对应的位置
题目重点：数组长度为n，每个元素的值都在[1，n]，数组下标是[0，n-1]。我们把元素i放在nums[i-1]的位置上。
③使用正负号作为标记
var findDuplicates = function(nums) {
const ans = [];
for(let i = 0; i < nums.length; i++) {
const x = Math.abs(nums[i]);
if(nums[x - 1] > 0){
nums[x - 1] = - nums[x - 1];
}else{
ans.push(x);
}
}
return ans;
};