leetcode每天5题-Day37

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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度：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;
};
1
2
3
4
5
6
7
8
9
10
11
12

空间复杂度是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;
};
1
2
3
4
5
6
7
8
9
10
11
12