数组篇四

56. 合并区间 - 力扣（LeetCode）

List.toArray()方法，将集合转化为数组

Arrays.sort(intervals, (a, b) -> a[0] - b[0]);将二维数组按照第一列的大小进行排序

方法一：将二维数组按照第一列的大小进行排序

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> ans = new ArrayList<>();
        for(int[] interval: intervals){
            int a = interval[0], b = interval[1];
            //如果ans为空 或者 （ans不为空）右边界小于新区间的左边界，则要添加新的区间
            if(ans.isEmpty() || ans.get(ans.size() - 1)[1] < a){
                ans.add(new int[]{a, b});
            }else{
                //不为空且要合成新的区间，比较右边边界
                ans.get(ans.size() - 1)[1] = Math.max(ans.get(ans.size() - 1)[1], b);
            }
        }
        return ans.toArray(new int[ans.size()][2]);
    }
}

方法二：将二维数组按照第二列的大小进行排序

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        int n = intervals.length;
        ArrayList<int[]> ret = new ArrayList<>();
        for(int i = n - 1; i >= 0; i--){
            int L = intervals[i][0], R = intervals[i][1];
            if(ret.isEmpty() || R < ret.get(ret.size() - 1)[0]){
                ret.add(new int[]{L, R});
            }else{
                ret.get(ret.size() - 1)[0] = Math.min(ret.get(ret.size() - 1)[0], L);
            }
        }
        return ret.toArray(new int[ret.size()][2]);
    }
}

2580. 统计将重叠区间合并成组的方案数 - 力扣（LeetCode）

方法一：将二维数组按照第一列的大小进行排序

class Solution {
    public int countWays(int[][] ranges) {
        Arrays.sort(ranges, (a, b) -> a[0]-b[0]);
        int n = ranges.length;
        int maxR = -1;
        int ans = 1;
        for(int i = 0; i < n; i++){
            int a = ranges[i][0], b = ranges[i][1];
            if(maxR < a) {
                ans = ans*2;
                ans %= 1000000007;
            }
            maxR = Math.max(b, maxR);
        }
        return ans;
    }
}

方法二：将二维数组按照第二列的大小进行排序

class Solution {
    public int countWays(int[][] ranges) {
        Arrays.sort(ranges,(a, b) -> a[1] - b[1]);
        //使用第二位数字进行排序时候，就要逆序遍历了
        int minL = Integer.MAX_VALUE, ans = 1;
        int n = ranges.length;
        for(int i = n - 1; i >= 0; i--){
            int L = ranges[i][0], R = ranges[i][1];
            if(minL > R){
                ans = ans*2;
                ans %= 1000000007;
            }
            minL = Math.min(minL, L);
        }
        return ans;
    }
}

2952. 需要添加的硬币的最小数量 - 力扣（LeetCode）

此题目对于思维能力感觉要求就是很高的那种，虽然它的代码及其简短（甚至都可以背得下来），但是代码是背不完的（除了排序），还是要对于代码具有一定的理解

• 对于一个整数x，如果区间[1, x - 1]内的所有金额都可以取的到，而且x还在数组之中，则区间[1, 2x - 1]内的所有金额也都可以取的到。

• 假设金额x不可取的，则至少要在数组中添加一个小于或者等于x的数组才能取得x，否则，无法取得x。

• 如果区间[1, x - 1]内的所有金额都可以取的到，则从贪心的角度来看，添加x之后则可以取得x，且满足添加的金额个数最少。在添加了x之后，区间 [1, 2x - 1]的所有金额都可以取的到，下一个不可取得的金额一定不会小于2x。

• 由此可以得到一个贪心的方案。每次找到不可取得的最小金额x，在数组之中添加x，之后，然后寻找下一个不可取得的最小整数，重复上述步骤，直到区间[1, target]中的所有金额都可以取得。

  具体实现方面，任何时候都应满足区间 [1,x−1] 内的所有金额都可取得。令 x 的初始值为 1，数组下标 index 的初始值为 0，则初始状态下区间 [1,x−1] 为空区间，满足区间内的所有金额都可取得。进行如下操作。

  • 如果 index 在数组 coins 的下标范围内且 coins[index]≤x，则将 coins[index] 的值加给 x，并将 index的值加 1。可取得的区间从[1,x−1] 扩展到 [1,x+coins[index]−1]，对 x 的值更新以后，可取得区间为 [1,x−1]。
  • 否则，x没有可取得，因此需要在数组中添加x，然后将 x 的值乘以2。
  • 在数组中添加 x之后，可取得的区间从[1,x−1]扩展到[1,2x−1]，对 x的值更新以后，可取得区间为[1,x−1]。
  • 重复上述操作，直到x的值大于 target。

class Solution {
    public int minimumAddedCoins(int[] coins, int target) {
        int n = coins.length,x = 1,index = 0,ans = 0;
        Arrays.sort(coins);
        while(x <= target){
            if(index < n && coins[index] <= x){
                x += coins[index];
                index++;
            }else{
                x *= 2;
                ans++;
            }
        }
        return ans;
    }
}

2007. 从双倍数组中还原原数组 - 力扣（LeetCode）

自己写的，之前从来没有注意过时间复杂度这个概念，然后毫无以外的超时了

• 1 <= changed.length <= 10^5
• 0 <= changed[i] <= 10^5

力扣上的题目的时间限制是1秒或2秒

n≤30, 指数级别, dfs+剪枝，状态压缩dp
n≤100 => O(n3)，floyd，dp
n≤1000 => O(n2)，O(n2logn)，dp，二分
分界点（一旦n到达1e4，就不适合n2的暴力解法）
n≤10000 => O(n∗√n)，块状链表
n≤100000 => O(nlogn) => 各种sort，线段树、树状数组、set/map、heap、dijkstra+heap、spfa、求凸包、求半平面交、二分
n≤1000000 => O(n), 以及常数较小的 O(nlogn) 算法 => hash、双指针扫描、kmp、AC自动机，常数比较小的 O(nlogn) 的做法：sort、树状数组、heap、dijkstra、spfa
n≤10000000 => O(n)，双指针扫描、kmp、AC自动机、线性筛素数
n≤10^9 => O(√n)，判断质数
n≤10^18 => O(logn)，最大公约数

很显然这个题目不能使用0（n^2）的时间复杂度来计算

class Solution {
    public int[] findOriginalArray(int[] changed) {
        int n = changed.length;
        if (n % 2 != 0)
            return new int[] {};
        int[] res = new int[n / 2];
        Arrays.sort(changed);
        boolean[] tag = new boolean[n];
        int idx = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (tag[i])
                continue;
            int t = 0;
            while (t <= n) {
                if (t == i){
                    t++;
                    continue;
                }
                if (t == n)
                    return new int[] {};
                if (!tag[t] && changed[t]*2 == changed[i]) {
                    tag[t] = true;
                    res[idx++] = changed[t];
                    break;
                }
                t++;
            }
        }
        return res;
    }
}

另一种解法：排序+哈希

时间复杂度（O(nlogn)）

排序的时间复杂度（O(nlogn)） 遍历数组的时间复杂度 O(n)

空间复杂度O(n)

class Solution {
    public int[] findOriginalArray(int[] arr) {
        Arrays.sort(arr);
        int n = arr.length;
        if(n % 2 != 0) return new int[0];
        int[] res = new int[n/2];
        HashMap<Integer, Integer> counts = new HashMap<>();
        for(int e : arr) counts.put(e, counts.getOrDefault(e, 0) + 1);
        int idx = 0;
        for(int e : arr){
            if(counts.get(e) == 0) continue;
            counts.put(e, counts.get(e)-1);
            if(counts.getOrDefault(2*e, 0) == 0) return new int[0];
            counts.put(2*e, counts.getOrDefault(e*2, 0) - 1);
            res[idx++] = e;
        }
        return res;
    }
}