排序.md

堆问题

​ 215. 数组中的第K个最大元素

​ 剑指Offer40. 最小的k个数

​ 347. 前 K 个高频元素

​ 451. 根据字符出现频率排序

​ 23. 合并K个升序链表

区间问题

​ 252. 会议室

​ 56. 合并区间

​ 57. 插入区间

​ 1288. 删除被覆盖区间

​ 435. 无重叠区间

​ 452. 用最少数量的箭引爆气球

思路

快速排序模板

private int partion(int[] nums, int left, int right) {
    if (right > left) {
        int randomIdx = left + random.nextInt(right - left + 1);
        swap(nums, left, randomIdx);
    }
    int pivot = left;
    while (left < right) {
        while (left < right && nums[right] > nums[pivot]) {
            right--;
        }  
        while (left < right && nums[left] <= nums[pivot]) {
            left++;
        }  
        swap(nums, left, right);
    }
    swap(nums, left, pivot);
    return right;
}

特别注意这里选用的退出循环条件是left < right时，快速排序要先走右指针。一定不能先走左指针。

这是为了避免极端特殊情况，例如[3,2,1,5,6,4]，pivot为3时，如果先走左边，左指针一直往右走直到5才停下来，右指针也一直往左走，直到5才停下来，右指针会同时停在5，交换之后，数组变成了[5,2,1,3,6,4]，顺序就不对了！应该让右指针多走一步，而不是左指针多走一步，所以右指针应该先走。如果右指针先走，停在1，左指针也停在1，交换之后是1,2,3,5,6,4，3前面都不大于3，3后面都不小于3，是正确的。

当然也可以换left<=right的条件，这时候可以先走left，再走right，不过需要加一个判断，如果left > right，就不要再交换left和right了。

private int partion(int[] nums, int left, int right) {
    if (left < right) {
        int randomIndex = left + random.nextInt(right - left + 1);
        swap(nums, left, randomIndex);
    }
    int pivot = left;
    while (left <= right) {
        while (left <= right && nums[left] <= nums[pivot]) {
            left++;  
        }
        while (left <= right && nums[right] > nums[pivot]) {
            right--;  
        }
        if (left > right) {
            break;
        }
        swap(nums, left, right);
    }
    swap(nums, right, pivot);
    return right;
}

选任意一种都可以，哪种熟练用哪种，不要记混或者增加减少条件就行。

堆问题

215. 数组中的第K个最大元素

Difficulty: 中等

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

**方法1：用类似于快速排序法的分治法。只在包含第k个元素的区间内进行快速排序，最终只剩下一个元素的时候就是第k个。**注意每次partition的时候随机交换，来避免正序数组或倒序数组的极端情况。

class Solution {
    private final Random random = new Random();
    public int findKthLargest(int[] nums, int k) {
        int left = 0, right = nums.length - 1;
        k = nums.length - k;
        while (left < right) {
            int pivot = partion(nums, left, right);
            if (pivot < k) {
                left = pivot + 1;   //不断缩小区间
            } else if (pivot > k) {
                right = pivot - 1;
            } else {
                return nums[pivot];
            }
        }
        return nums[left];
    }

    private int partion(int[] nums, int left, int right) {
        if (right > left) {
            int randomIdx = left + random.nextInt(right - left + 1);
            swap(nums, left, randomIdx);
        }
        int pivot = left;
        while (left < right) {
            while (left < right && nums[right] > nums[pivot]) {
                right--;
            }  
            while (left < right && nums[left] <= nums[pivot]) {
                left++;
            }  
            swap(nums, left, right);
        }
        swap(nums, left, pivot);
        return right;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

**方法2：用PQ。求最大，维持一个最小堆，求第k大，只需要把最大的k个数都放进堆中，最小的那个数就是第k大的。**先放进去k个，然后继续遍历，如果比堆顶大，把堆顶poll出来，把当前加进去。

用PQ的好处是堆的空间一直是k个，不需要一次性把所有元素都加到内存中，只需要k个。这也是为什么堆常用来处理特别大量数据的排序问题。

public int findKthLargest(int[] nums, int k) {
    // 使用一个含有 k 个元素的最小堆
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);
    for (int i = 0; i < k; i++) {
        minHeap.add(nums[i]);
    }
    for (int i = k; i < nums.length; i++) {
        // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
        if (nums[i] > minHeap.peek()) {
            minHeap.poll();
            minHeap.add(nums[i]);
        }
    }
    return minHeap.peek();
}

剑指Offer40. 最小的k个数

Difficulty: 简单

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：

• 0 <= k <= arr.length <= 10000
• 0 <= arr[i] <= 10000

**思路：**与215. 数组中的第K个最大元素相同，分治法如果pivot==k可以提前退出循环。堆方法更简单，这里就不写了。

public int[] getLeastNumbers(int[] arr, int k) {
    int left = 0, right = arr.length - 1, pivot = -1;
    //除了left == right，此时找到第k小，还要加上pivot != k，如果pivot等于k，[0,pivot]即为最小的k个数。
    while (left < right && pivot != k) {
        pivot = partion(arr, left, right);
        if (pivot < k) {
            left = pivot + 1;   
        } else if (pivot > k) {
            right = pivot - 1;
        }
    }
    int[] res = new int[k];
    for(int i = 0; i < k; i++){
        res[i] = arr[i];
    }
    return res;
}

private int partion(int[] nums, int left, int right) {
    //与215. 数组中的第K个最大元素相同
}

private void swap(int[] nums, int i, int j) {
    //与215. 数组中的第K个最大元素相同
}

如题解，还可以用TreeMap，计数排序。

347. 前K个高频元素

美团实习一面考到

Difficulty: 中等

给定一个非空的整数数组，返回其中出现频率前 **_k _**高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

• 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
• 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
• 你可以按任意顺序返回答案。

思路：求大的k个，用最小堆。

public int[] topKFrequent(int[] nums, int k) {
    HashMap<Integer, Integer> map = new HashMap<>(nums.length);
    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }
    // 遍历map，用最小堆保存频率最大的k个元素
    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> map.get(a) - map.get(b));
    for (int key : map.keySet()) {
        if (pq.size() < k) {
            pq.add(key);
        } else if (map.get(key) > map.get(pq.peek())) {
            pq.poll();
            pq.add(key);
        }
    }
    // 取出最小堆中的元素
    int[] res = new int[k];
    for (int i = k - 1; i >= 0; i--) {
        res[i] = pq.poll();
    }
    return res;
}

注意：如果想用数组的排序，但是数组的排序要求Comparator返回类型和数组元素类型相同，如果是Integer数组，才可以使用Arrays.sort(nums, (a, b) -> (map.get(a) - map.get(b)));。

其他方法：

可以使用桶排序，桶的数量是nums.length+1，把频率相同的都放到对应index的链表中。

Todo：659. 分割数组为连续子序列

451. 根据字符出现频率排序

Difficulty: 中等

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

示例 1:

输入:
"tree"

输出:
"eert"

解释:
'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

示例 2:

输入:
"cccaaa"

输出:
"cccaaa"

解释:
'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。

示例 3:

输入:
"Aabb"

输出:
"bbAa"

解释:
此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。

**思路：**和347. 前 K 个高频元素相同。

	public String frequencySort(String s) {
        int[] letters = new int[128];
        for (char c : s.toCharArray()) letters[c]++;

        PriorityQueue<Character> heap = new PriorityQueue<>(128, (a, b) -> Integer.compare(letters[b], letters[a]));
        StringBuilder res = new StringBuilder();

        for (int i = 0; i < letters.length; ++i) {
            if (letters[i] != 0) {
                heap.offer((char) i);
            }
        }

        while (!heap.isEmpty()) {
            char c = heap.poll();
            while (letters[c]-- > 0) {
                res.append(c);
            }
        }
        return res.toString();
    }

23. 合并K个升序链表

Difficulty: 困难

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

归并：

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) {
        return null;
    }
    return mergeKLists(lists, 0, lists.length - 1);
}

private ListNode mergeKLists(ListNode[] lists, int left, int right) {
    if (left == right) {
        return lists[left];
    }
    int mid = left + (right - left) / 2; //int mid = (left+right)>>>1;
    return merge(mergeKLists(lists, left, mid), mergeKLists(lists, mid + 1, right));
}

private ListNode merge(ListNode l1, ListNode l2) {
    if (l1 == null || l2 == null) {
        return l1 == null ? l2 : l1;
    }
    if (l1.val < l2.val) {
        l1.next = merge(l1.next, l2);
        return l1;
    } else {
        l2.next = merge(l1, l2.next);
        return l2;
    }
}

PQ：

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
        @Override
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }
    });
    ListNode dummy = new ListNode(0);
    ListNode p = dummy;
    for (ListNode node : lists) {
        if (node != null) queue.add(node);
    }
    while (!queue.isEmpty()) {
        p.next = queue.poll();
        p = p.next;
        if (p.next != null) queue.add(p.next);
    }
    return dummy.next;
}

//或者用lambda表达式
public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, 
                                                        (a,b)-> (a.val - b.val)
                                                       );
    ListNode dummy = new ListNode(0);
    ListNode p = dummy;
    for (ListNode node : lists) {
        if (node != null) queue.add(node);
    }
    while (!queue.isEmpty()) {
        p.next = queue.poll();
        p = p.next;
        if (p.next != null) queue.add(p.next);
    }
    return dummy.next;
}

区间问题

252. 会议室

Difficulty: 简单

给定一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间intervals[i] = [start_i, end_i]`，请你判断一个人是否能够参加这里面的全部会议。

示例 1：

输入：intervals = [[0,30],[5,10],[15,20]]
输出：false

示例 2：

输入：intervals = [[7,10],[2,4]]
输出：true

提示：

• 0 <= intervals.length <= 10⁴
• intervals[i].length == 2
• 0 <= start_i < end_i <= 10⁶

**思路：**将区间按照会议开始实现升序排序，遍历会议，如果下一个会议在前一个会议结束之前就开始了，就不能。

	public boolean canAttendMeetings(int[][] intervals) {
        // 将区间按照会议开始实现升序排序
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
        // 遍历会议，如果下一个会议在前一个会议结束之前就开始了，返回 false。
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false;
            }
        }
        return true;
    }

56. 合并区间

Difficulty: 中等

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start_i, end_i] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 10⁴
• intervals[i].length == 2
• 0 <= start_i <= end_i <= 10⁴

思路：按照起始位置排序，然后合并即可。

    public int[][] merge(int[][] intervals) {
        // 先按照区间起始位置排序
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
        // 遍历区间
        int[][] res = new int[intervals.length][2];
        int idx = -1;
        for (int[] interval : intervals) {
            // 如果结果数组是空的，或者当前区间的起始位置 > 结果数组中最后区间的终止位置，
            // 则不合并，直接将当前区间加入结果数组。
            if (idx == -1 || interval[0] > res[idx][1]) {
                res[++idx] = interval;
            } else {
                // 反之将当前区间合并至结果数组的最后区间
                res[idx][1] = Math.max(res[idx][1], interval[1]);
            }
        }
        return Arrays.copyOf(res, idx + 1);
    }

57. 插入区间

Difficulty: 中等

给你一个 无重叠的按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例 1：

输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]

示例 2：

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

示例 3：

输入：intervals = [], newInterval = [5,7]
输出：[[5,7]]

示例 4：

输入：intervals = [[1,5]], newInterval = [2,3]
输出：[[1,5]]

示例 5：

输入：intervals = [[1,5]], newInterval = [2,7]
输出：[[1,7]]

提示：

• 0 <= intervals.length <= 10⁴
• intervals[i].length == 2
• 0 <= intervals[i][0] <= intervals[i][1] <= 10⁵
• intervals 根据 intervals[i][0] 按 升序 排列
• newInterval.length == 2
• 0 <= newInterval[0] <= newInterval[1] <= 10⁵

思路：区间已经排序好了，直接遍历插入进去合适的位置即可。

	public int[][] insert(int[][] intervals, int[] newInterval) {
        int[][] res = new int[intervals.length + 1][2];
        int idx = 0;
        // 遍历区间列表：
        // 首先将新区间左边且相离的区间加入结果集
        int i = 0;
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            res[idx++] = intervals[i++];
        }
        // 接着判断当前区间是否与新区间重叠，重叠的话就进行合并，直到遍历到当前区间在新区间的右边且相离，
        // 将最终合并后的新区间加入结果集
        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
            newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
            i++;
        }
        res[idx++] = newInterval;
        // 最后将新区间右边且相离的区间加入结果集
        while (i < intervals.length) {
            res[idx++] = intervals[i++];
        }

        return Arrays.copyOf(res, idx);
    }

1288. 删除被覆盖区间

Difficulty: 中等

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。

只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。

在完成所有删除操作后，请你返回列表中剩余区间的数目。

示例：

输入：intervals = [[1,4],[3,6],[2,8]]
输出：2
解释：区间 [3,6] 被区间 [2,8] 覆盖，所以它被删除了。

提示：

• 1 <= intervals.length <= 1000
• 0 <= intervals[i][0] < intervals[i][1] <= 10^5
• 对于所有的 i != j：intervals[i] != intervals[j]

思路：排序+贪心。

主要按照左端点升序，相同左端点按照右端点降序。然后顺序遍历数组，前面的左端点已经包含后面的左端点了，只需要判断前面的右端点是不是包括后面的右端点。

public int removeCoveredIntervals(int[][] intervals) {
    int len = intervals.length;
    // 特判
    if (len < 2) {
        return len;
    }

    // 特别注意：当区间左端点相同的时候，右端点降序排序
    Arrays.sort(intervals, (v1, v2) -> {
        if (v1[0] == v2[0]) {
            return v2[1] - v1[1];
        }
        return v1[0] - v2[0];
    });

    // 需要被删除的区间个数
    int remove = 0;
    int end = intervals[0][1];
    System.out.print(end);
    for (int i = 1; i < len; i++) {
        if (intervals[i][1] <= end) {
            remove++;
        } else {
            end = intervals[i][1];
        }
    }
    return len - remove;
}

​

435. 无重叠区间

Difficulty: 中等

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

1. 可以认为区间的终点总是大于它的起点。
2. 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

示例 1:

输入: [ [1,2], [2,3], [3,4], [1,3] ]

输出: 1

解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

输入: [ [1,2], [1,2], [1,2] ]

输出: 2

解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: [ [1,2], [2,3] ]

输出: 0

解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

思路：贪心法。按照起始排序，遍历所有区间，遇到重叠就删除。为了不与后面的重叠，end越小越好，因此保存现在最小的end。

如果当前的起始小于end，说明重叠了，删除哪个呢？end越小越好，删除end大的。

按照结尾排序也可以。

public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0)
        return 0;
    //先排序
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    //记录区间尾部的位置
    int end = intervals[0][1];
    //需要移除的数量
    int count = 0;
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < end) {
            //如果重叠了，必须要移除一个，所以count要加1，
            //然后更新尾部的位置，取尾部比较小的
            end = Math.min(end, intervals[i][1]);
            count++;
        } else {
            //如果没有重叠，就不需要移除，只需要更新尾部的位置即可
            end = intervals[i][1];
        }
    }
    return count;
}

这道题也可以抽象成300. 最长递增子序列，递增的规则是当前的start大于前面的end。了解即可，主要掌握贪心法。

public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0) {
        return 0;
    }

    Arrays.sort(intervals, new Comparator<int[]>() {
        public int compare(int[] interval1, int[] interval2) {
            return interval1[0] - interval2[0];
        }
    });

    int n = intervals.length;
    int[] f = new int[n];
    Arrays.fill(f, 1);
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (intervals[j][1] <= intervals[i][0]) {
                f[i] = Math.max(f[i], f[j] + 1);
            }
        }
    }
    return n - Arrays.stream(f).max().getAsInt();
}

作者：LeetCode-Solution

452. 用最少数量的箭引爆气球

Difficulty: 中等

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。

一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x_start，x_end， 且满足 x_start ≤ x ≤ x_end，则该气球会被引爆_。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

给你一个数组 points ，其中 points [i] = [x_start,x_end] ，返回引爆所有气球所必须射出的最小弓箭数。

示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球

示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4

示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2

示例 4：

输入：points = [[1,2]]
输出：1

示例 5：

输入：points = [[2,3],[2,3]]
输出：1

提示：

• 0 <= points.length <= 10⁴
• points[i].length == 2
• -2³¹ <= x_start < x_end <= 2³¹ - 1

思路：排序+贪心法。

按照右边界从小到大排序。射右边界end，如果后面的起始在当前右边界左边，可以被射到。否则不能射到，需要更新end，再射end。

图片作者：sdwwld

public int findMinArrowShots(int[][] points) {
    //边界条件判断
    if (points == null || points.length == 0)
        return 0;
    //按照每个气球的右边界排序
    Arrays.sort(points, (a, b) -> a[1] > b[1] ? 1 : -1);
    //获取排序后第一个气球右边界的位置，我们可以认为是箭射入的位置
    int end = points[0][1];
    //统计箭的数量
    int count = 1;
    for (int i = 1; i < points.length; i++) {
        //如果箭射入的位置小于下标为i这个气球的左边位置，说明这支箭不能
        //击爆下标为i的这个气球，需要再拿出一支箭，并且要更新这支箭射入的
        //位置
        if (end < points[i][0]) {
            end = points[i][1];
            count++;
        }
    }
    return count;
}