• 基础知识：快速排序（Quick Sort）， 归并排序（Merge Sort）的原理与代码实现。需要能讲明白代码中每一行的目的。快速排序时间复杂度平均状态下O（NlogN），空间复杂度O（1），归并排序最坏情况下时间复杂度O（NlogN），空间复杂度O（N）
• 入门题目：

Leetcode 148. Sort List

Leetcode 56. Merge Intervals

Leetcode 27. Remove elements

• 进阶题目：

Leetcode 179. Largest Number

Leetcode 75. Sort Colors

Leetcode 215. Kth Largest Element （可以用堆的解法替代）

Leetcode 4. Median of Two Sorted Arrays

注意：后两题是与快速排序非常相似的快速选择（Quick Select）算法，面试中很常考

提问模版

现在你的身份是ACM高手，你需要模拟成正在被上机考试，你需要用空间和时间复杂度最低的方式，使用JAVA语言，用题目+样例+代码+解释的模版解答leetcode问题, 使用markdown进行作答，请用类似这样的markdown语言作答:"## 题目描述 给定一组非负整数 nums，重新排列它们每个数字的顺序（每个数字不可拆分）使之组成一个最大的整数。 **注意：**输出结果可能非常大，所以你需要返回一个字符串而不是整数。 示例 1： 输入：nums = [10,2] 输出："210" 示例 2： 输入：nums = [3,30,34,5,9] 输出："9534330" 示例 3： 输入：nums = [1] 输出："1" 示例 4： 输入：nums = [10] 输出："10" 提示： - 1 <= nums.length <= 100 - 0 <= nums[i] <= 10^9 ## 解法 本题的解法是将所有数字转换成字符串，然后按照字符串的大小关系进行排序。排序时，对于两个字符串 $aa$ 和 $bb$，如果 $a+b>b+aa+b\; >\; b+a$，则将 $aa$ 排在 $bb$ 前面，否则将 $bb$ 排在 $aa$ 前面。最后将所有字符串拼接起来即可。 ## 代码 java class Solution { public String largestNumber(int[] nums) { String[] strs = new String[nums.length]; for (int i = 0; i < nums.length; i++) { strs[i] = String.valueOf(nums[i]); } Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b)); if (strs[0].equals("0")) { return "0"; } StringBuilder sb = new StringBuilder(); for (String str : strs) { sb.append(str); } return sb.toString(); } } ## 复杂度分析 时间复杂度：$O(nlogn)O(nlogn)$，其中 $nn$ 是数组的长度。排序的时间复杂度是 $O(nlogn)O(nlogn)$。 空间复杂度：$O(n)O(n)$，其中 $nn$ 是数组的长度。需要使用额外的空间存储所有数字的字符串表示。"

Leetcode 148. Sort List

题目描述

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶：

• 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例 1：

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

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

解法

本题的解法是归并排序。首先将链表分成两个部分，然后对这两个部分分别进行排序，最后将两个有序链表合并成一个有序链表。

代码

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(mid);
        return merge(left, right);
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 != null ? l1 : l2;
        return dummy.next;
    }
}

复杂度分析

时间复杂度：$O(nlogn)O(nlogn)$，其中 $nn$ 是链表的长度。对链表进行归并排序的时间复杂度是 $O(nlogn)O(nlogn)$，其中分割链表和合并链表的时间复杂度均为 $O(logn)O(logn)$。

空间复杂度：$O(logn)O(logn)$，其中 $nn$ 是链表的长度。空间复杂度主要取决于递归调用的栈空间，每次递归调用都会将链表平均分割成两半，递归调用的层数为 $O(logn)O(logn)$，因此空间复杂度为 $O(logn)O(logn)$。

Leetcode 56. Merge Intervals

题目描述

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

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

示例 2:

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

解法

本题的解法是先将所有区间按照左端点从小到大排序，然后遍历所有区间，如果当前区间的左端点小于等于上一个区间的右端点，则说明两个区间有重叠，将它们合并，否则将当前区间加入答案数组中。

代码

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> res = new ArrayList<>();
        int[] cur = intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            if (cur[1] >= intervals[i][0]) {
                cur[1] = Math.max(cur[1], intervals[i][1]);
            } else {
                res.add(cur);
                cur = intervals[i];
            }
        }
        res.add(cur);
        return res.toArray(new int[res.size()][2]);
    }
}

复杂度分析

时间复杂度：$O(nlogn)O(nlogn)$，其中 $nn$ 是区间的数量。除去排序的开销，我们只需要一次线性扫描，所以主要的时间开销是排序的 $O(nlogn)O(nlogn)$。

空间复杂度：$O(logn)O(logn)$，其中 $nn$ 是区间的数量。这里计算的是存储答案之外，使用的额外空间。$O(logn)O(logn)$ 即为排序所需要的空间复杂度。如果已经排好序，则不需要额外的存储空间，空间复杂度为 $O(1)O(1)$。

Leetcode 27. Remove elements

题目描述

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0、1、3、0 和 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

解法

本题的解法是使用双指针。定义两个指针 i 和 j，初始时 i = 0，j = 0。遍历数组，如果当前元素不等于 val，则将其赋值给 nums[i]，并将 i 加一；否则，将 j 加一。最后返回 i 即可。

代码

class Solution {
    public int removeElement(int[] nums, int val) {
        int i = 0;
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] != val) {
                nums[i] = nums[j];
                i++;
            }
        }
        return i;
    }
}

复杂度分析

时间复杂度：$O(n)O(n)$，其中 $nn$ 是数组的长度。只需要遍历一次数组即可。

空间复杂度：$O(1)O(1)$。只需要常数的额外空间。

Leetcode 179. Largest Number

题目描述

给定一组非负整数 nums，重新排列它们每个数字的顺序（每个数字不可拆分）使之组成一个最大的整数。

**注意：**输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例 1：

输入：nums = [10,2]
输出："210"

示例 2：

输入：nums = [3,30,34,5,9]
输出："9534330"

示例 3：

输入：nums = [1]
输出："1"

示例 4：

输入：nums = [10]
输出："10"

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 10^9

解法

本题的解法是将所有数字转换成字符串，然后按照字符串的大小关系进行排序。排序时，对于两个字符串 $aa$ 和 $bb$，如果 $a+b>b+aa+b\; >\; b+a$，则将 $aa$ 排在 $bb$ 前面，否则将 $bb$ 排在 $aa$ 前面。最后将所有字符串拼接起来即可。

代码

class Solution {
    public String largestNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));
        if (strs[0].equals("0")) {
            return "0";
        }
        StringBuilder sb = new StringBuilder();
        for (String str : strs) {
            sb.append(str);
        }
        return sb.toString();
    }
}

复杂度分析

时间复杂度：$O(nlogn)O(nlogn)$，其中 $nn$ 是数组的长度。排序的时间复杂度是 $O(nlogn)O(nlogn)$。

空间复杂度：$O(n)O(n)$，其中 $nn$ 是数组的长度。需要使用额外的空间存储所有数字的字符串表示。

Leetcode 75. Sort Colors

题目描述

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。

进阶：

• 你可以不使用代码库中的排序函数来解决这道题吗？
• 你能想出一个仅使用常数空间的一趟扫描算法吗？

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

示例 3：

输入：nums = [0]
输出：[0]

示例 4：

输入：nums = [1]
输出：[1]

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

解法

本题的解法是使用三指针。定义三个指针 p0、p1 和 p2，分别表示下一个要放置 0、1 和 2 的位置。初始时，p0 = 0，p1 = 0，p2 = n - 1。遍历数组，如果当前元素为 0，则将其放置在 p0 的位置，并将 p0 和 p1 都加一；如果当前元素为 1，则将其放置在 p1 的位置，并将 p1 加一；如果当前元素为 2，则将其放置在 p2 的位置，并将 p2 减一。直到 p1 > p2 为止。

代码

class Solution {
    public void sortColors(int[] nums) {
        int p0 = 0, p1 = 0, p2 = nums.length - 1;
        while (p1 <= p2) {
            if (nums[p1] == 0) {
                swap(nums, p0, p1);
                p0++;
                p1++;
            } else if (nums[p1] == 1) {
                p1++;
            } else {
                swap(nums, p1, p2);
                p2--;
            }
        }
    }

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

复杂度分析

时间复杂度：$O(n)O(n)$，其中 $nn$ 是数组的长度。只需要遍历一次数组即可。

空间复杂度：$O(1)O(1)$。只需要常数的额外空间。

Leetcode 215. Kth Largest Element

题目描述

在未排序的数组中找到第 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 ≤ 数组的长度。

解法

本题可以使用快速排序的思想来解决。我们可以先将数组进行一次快速排序，然后找到排序后第 k 个最大的元素即可。

快速排序的思想是：选择一个基准元素，将数组分为两部分，一部分是小于基准元素的，一部分是大于基准元素的。然后对这两部分分别进行快速排序，直到数组有序。

在本题中，我们可以选择数组的最后一个元素作为基准元素，然后将数组分为两部分，一部分是小于基准元素的，一部分是大于基准元素的。如果大于基准元素的部分的长度小于 k，则说明第 k 个最大的元素在小于基准元素的部分中，否则在大于基准元素的部分中。然后对应的部分进行递归即可。

代码

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, k);
    }

    private int quickSelect(int[] nums, int left, int right, int k) {
        int pivot = nums[right];
        int i = left;
        for (int j = left; j < right; j++) {
            if (nums[j] > pivot) {
                swap(nums, i, j);
                i++;
            }
        }
        swap(nums, i, right);
        int count = i - left + 1;
        if (count == k) {
            return nums[i];
        } else if (count > k) {
            return quickSelect(nums, left, i - 1, k);
        } else {
            return quickSelect(nums, i + 1, right, k - count);
        }
    }

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

复杂度分析

时间复杂度：平均时间复杂度为 $O(n)O(n)$，最坏时间复杂度为 $O(n^2)O(n^2)$，其中 $nn$ 是数组的长度。快速排序的时间复杂度为 $O(nlogn)O(nlogn)$，但是在最坏情况下，每次划分只能将数组分为一个元素和 $n-1n-1$ 个元素两部分，因此需要进行 $nn$ 次划分，时间复杂度为 $O(n^2)O(n^2)$。

空间复杂度：$O(logn)O(logn)$，其中 $nn$ 是数组的长度。快速排序的空间复杂度为 $O(logn)O(logn)$，因为需要使用递归栈。

Leetcode 4. Median of Two Sorted Arrays

题目描述

给定两个大小为 $mm$ 和 $nn$ 的排序数组 nums1 和 nums2，请找出两个排序数组的中位数并且总的运行时间复杂度应为 $O(\log (m+n))O(\backslash log(m+n))$。

你可以假设 nums1 和 nums2 不会同时为空。

示例1：

nums1 = [1, 3]
nums2 = [2]

中位数是 2.0

示例2：

nums1 = [1, 2]
nums2 = [3, 4]

中位数是 (2 + 3)/2 = 2.5

解法

方法一：暴力法

最简单直接的思路就是将两个数组合并成一个有序数组，然后根据数组的长度奇偶性来直接找出中位数。

时间复杂度：$O(m+n)O(m\; +\; n)$

空间复杂度：$O(m+n)O(m\; +\; n)$

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] nums = new int[m + n];
        int i = 0, j = 0, k = 0;
        while(i < m && j < n) {
            nums[k++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
        }
        while(i < m) {
            nums[k++] = nums1[i++];
        }
        while(j < n) {
            nums[k++] = nums2[j++];
        }
        if((m + n) % 2 == 0) {
            return (nums[(m + n) / 2 - 1] + nums[(m + n) / 2]) / 2.0;
        } else {
            return nums[(m + n) / 2];
        }
    }
}

方法二：二分法

由于题目中规定时间复杂度为 $O(\log (m+n))O(\backslash log(m\; +\; n))$，因此不能使用直接合并两个数组的方式，该算法思想就是采用二分法，按照数组长度较小的那一个进行二分查找，然后另一个数组也进行二分查找，以此来逐渐缩小中位数的取值区间，最终得到中位数。

时间复杂度：$O(\log \min (m,n))O(\backslash log\backslash min(m,\; n))$

空间复杂度：$O(1)O(1)$

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1.length > nums2.length) {
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }
        int m = nums1.length;
        int n = nums2.length;
        int left = 0, right = m, mid = 0, i = 0, j = 0, maxLeft = 0, minRight = 0;
        while(left <= right) {
            mid = (left + right) / 2;
            i = mid;
            j = (m + n + 1) / 2 - i;
            if(i > 0 && nums1[i - 1] > nums2[j]) {
                right = mid - 1;
            } else if(i < m && nums2[j - 1] > nums1[i]) {
                left = mid + 1;
            } else {
                if(i == 0) {
                    maxLeft = nums2[j - 1];
                } else if(j == 0) {
                    maxLeft = nums1[i - 1];
                } else {
                    maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
                }
                break;
            }
        }
        if((m + n) % 2 == 1) {
            return maxLeft;
        }
        if(i == m) {
            minRight = nums2[j];
        } else if(j == n) {
            minRight = nums1[i];
        } else {
            minRight = Math.min(nums1[i], nums2[j]);
        }
        return (maxLeft + minRight) / 2.0;
    }
}

复杂度分析

方法一：

由于需要先将数组 nums1 和 nums2 合并成一个有序数组，因此时间复杂度为 $O(m+n)O(m\; +\; n)$，空间复杂度也是 $O(m+n)O(m\; +\; n)$。

方法二：

为了降低时间复杂度，我们选择采用二分法。在遍历过程中，每次将长度较小的数组进行二分，因此时间复杂度为 $O(\log \min (m,n))O(\backslash log\backslash min(m,\; n))$，而空间复杂度为 $O(1)O(1)$。