排序.md

剑指offer45，把数组排成最小的数，中等

核心方法：如果将所有可能的结果都排出来，再进行排序，那么可能面临着数值溢出的异常问题。这里可以使用冒泡排序的最佳优化方式，核心在于将两两排列最大的放到尾部，这样算法收敛后就能够排列出最小的数字。字符串a+b大于b+a的情况下，则交换a和b。

• 比如 "210" > "102"，那么一定能得到 210 > 102 么？

  答案是肯定的：首先拼接成的两个字符串一定是等长的。等长的字符串在比较的时候，是按照字符串的各个字符从前向后逐个比较的，所以相当于先比较了百分位，然后比较十分位，最后比较个位。所以在字符串等长的情况下，字符串大，那么对应的整型也更大。但两个不等长的字符串就没有这个结论了， 比如 "2" > "10"，但是 2 < 10。

时间复杂度：$O(n^2)$

空间复杂度：O(1)

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        n = len(nums)
        swapped = True
        last_idx = n - 1      # 最后一个没有经过排序的元素下标
        swapped_idx = -1      # 上次发生交换的位置
        while swapped:        # 上一步没有交换时，这一步退出while循环
            swapped = False
            for i in range(last_idx):
                if str(nums[i]) + str(nums[i+1]) > str(nums[i+1]) + str(nums[i]):
                    tmp = nums[i]
                    nums[i] = nums[i+1]
                    nums[i+1] = tmp
                    swapped = True
                    swapped_idx = i    # 每轮只要发生了交换，就维护一次发生交换的位置
            last_idx = swapped_idx # 最后一个没有经过排序的元素下标就是最后一次发生交换的位置
        nums = [str(item) for item in nums]
        return ''.join(nums)

179，最大数，中等

核心方法：和上一个【把数组排成最小数】的解法都一样，都使用了【冒泡排序】，只需要把中间的交换条件修改为当前的两个排列的组合小于修改顺序后的两个排列时，再进行交换。要注意的是如果最后得到的字符串为多个0，那么返回只需要返回一个0，因为多个0在数字中是不合法的。

时间复杂度：$O(n^2)$

空间复杂度：O(1)

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        # 使用冒泡排序
        n = len(nums)
        swapped = True
        last_idx = n - 1
        swapped_idx = -1
        while swapped:
            swapped = False
            for i in range(last_idx):
                if str(nums[i]) + str(nums[i+1]) < str(nums[i+1]) + str(nums[i]):
                    tmp = nums[i]
                    nums[i] = nums[i+1]
                    nums[i+1] = tmp
                    swapped = True
                    swapped_idx = i
            last_idx = swapped_idx
        nums = [str(item) for item in nums]
        if set(nums) == {'0'}: return '0'
        return ''.join(nums)

283，移动零，

核心方法：双指针。两个指针同时向前走，如果一个指向的非零元素，一个指向0，那么就交换两个元素。指向非零元素的指针在每轮循环中都要移动，但只要指向非零的指针指向非零元素，那么就移动指向零的指针。也就是说，这种算法会使得前面所有的零全部移到数组最后的位置。

时间复杂度：O(n)

空间复杂度：O(1)

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i, j = 0, 0
        while j < len(nums):
            if nums[j] != 0:
                if nums[i] == 0:
                    # 进行交换，前提是一个指针指向非零，一个指向0
                    nums[i] = nums[j]
                    nums[j] = 0
                i +=1
            j += 1
        return nums

912，排序数组，中等

核心方法：使用希尔排序。

• 时间复杂度：它的平均复杂度界于 $O(n)$ 到 $O(n^2)$ 之间，普遍认为它最好的时间复杂度为 $O(n^{1.3})$

• 空间复杂度为 O(1)，只需要常数级的临时变量

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        gap = n // 2  # 间隔序列，在希尔排序中我们称之为增量序列
        while gap > 0:
            # 相比【插入排序】，主要变化是在最外层嵌套了一个缩小增量的 for 循环；并且插入时不再是相邻数字挪动，而是以增量为步长挪动。
            # 从 gap 开始，按照顺序将每个元素依次向前插入自己所在的组
            for i in range(gap, n):
                # 当前待插入的元素
                curr = nums[i]
                # 该组前一个数字的索引
                preIdx = i - gap
                while preIdx >= 0 and curr < nums[preIdx]:
                    # 将大于当前元素的元素向后移
                    nums[preIdx + gap] = nums[preIdx]
                    preIdx -= gap
                nums[preIdx + gap] = curr
            gap = gap // 2
        return nums

核心方法：快速排序（推荐）

• 介绍：

  • 通过划分将待排序的序列分成前后两部分，其中前一部分的数据都比后一部分的数据要小，然后再递归调用函数对两部分的序列分别进行快速排序，以此使整个序列达到有序。

• 递归函数：

  • 函数randomized_quicksort(nums, l ,r)为对nums数组里的[l, r]的部分进行排序，每次先调用划分函数randomized_partition对nums数组里的[l, r]的部分进行划分，并返回分界值的下标pos，然后记录递归调用randomized_quicksort(nums, l ,pos-1)和randomized_quicksort(nums, pos-1, r)

• 划分函数：

  • 初始状态下需要确定第一个分界值，称之为pivot。这里使用随机划分的方法，对当前划分区间 [l, r] 里的数等概率随机一个作为我们的主元。再将主元放到区间末尾，进行划分。
  • 整个划分函数 partition 主要涉及两个指针 i 和 j，一开始 i = l - 1，j = l。我们需要实时维护两个指针使得任意时候，对于任意数组下标 k，我们有如下条件成立：
    1. $l \le k \le i$ 时， $nums[k] \le pivot$
    2. $i+1 \le k \le j-1$ 时， $nums[k] &gt; pivot$
    3. $k == r$ 时，$nums[k] = pivot$
  •  后续的操作就是要让每一次排序完的数组满足上述条件 
  • 每次开始排序前，j从l开始遍历，如果nums[j]小于nums[r]，那么i+=1；由于i的初始值为-1，当+1后就会变为0，然后nums[0]就可以取值了。这时对nums[i]和nums[j]进行交换，交换时，nums[j]表示当前遍历位置处小于nums[r]（也就是pivot，这里已经进行了交换）的数，nums[i]表示从左至右第一个大于nums[r]的数。遍历完成后，就能在i处形成一个区分，nums[0..i]处为小于pivot的，nums[i+1..n-2]处为大于pivot。
  • 此时i需要向前走一步，走这一步是为了将nums[i]与nums[r]进行交换，也就是nums[i]与pivot（中间值）进行交换，这样从左到右最大的数就被换到了末尾。交换完成后，pivot对应的索引就是i，i的左边都是小于pivot的，i的右边都是大于pivot的，此时的区间就划分好了。

• 时间复杂度：O(nlogn)

• 空间复杂度：O(h)，其中h为快速排序中递归调用的层数。由于划分的结果不同导致了快速排序递归调用的层数也会不同，最坏情况下需 O(n) 的空间，最优情况下每次都平衡，此时整个递归树高度为 logn，空间复杂度为 O(logn)。

class Solution:
    def randomized_partition(self, nums, l, r):
        # 随机选取数组中的一个数作为pivot
        pivot = random.randint(l, r)  
        # 将【pivot】与【末尾元素】进行交换
        nums[pivot], nums[r] = nums[r], nums[pivot]
        i = l - 1
        for j in range(l, r):
            if nums[j] < nums[r]:
                i += 1
                # 【最靠前的大数】与【当前遍历到的小数】进行交换
                nums[j], nums[i] = nums[i], nums[j]
        i += 1
        # 【当前最靠前的大数】与【末尾pivot】进行交换
        nums[i], nums[r] = nums[r], nums[i]
        # 返回的是【当前pivot】
        return i

    def randomized_quicksort(self, nums, l, r):
        if r - l <= 0:
            return
        mid = self.randomized_partition(nums, l, r)
        self.randomized_quicksort(nums, l, mid - 1)
        self.randomized_quicksort(nums, mid + 1, r)

    def sortArray(self, nums: List[int]) -> List[int]:
        self.randomized_quicksort(nums, 0, len(nums) - 1)
        return nums

核心方法：堆排序。

首先将待排序的序列构建最大堆。使得每个父节点的元素都大于子节点的元素。序列最大值为堆顶元素，然后将其与末尾元素进行交换，使末尾元素为最大值。在调整堆顶元素使得剩下的n-1个元素仍为最大堆。重复上述步骤。

总结起来是两步，首先进行堆化，然后取出最大值后，重新进行堆化，直到堆为空

• 完全二叉树的性质
  • 完全二叉树的第 i 个节点，其左子节点索引为 left = 2 * i - 1，右子节点为 right = left + 1
• 时间复杂度：O(nlogn)
• 空间复杂度：O(1)

class Solution:
    def max_heapify(self, heap, root, heap_len):
        """
        构建最大堆
        Arguments:
        	heap: 数组元素
        	root: 当前在排的元素的索引
        	heap_len: 未排序的数组长度，也就是为排序的元素个数
        """
        p = root  # 当前节点（根节点）的索引
        while p * 2 + 1 < heap_len:  # 需要保证当前左子节点的索引不超过为排序的元素个数
            # 分别定义左子节点和右子节点
            l, r = p * 2 + 1, p * 2 + 2
            
            # 找到根结点，左子节点，右子节点的最大值
            # nex 用来记录左子结点、右子结点二者中的最大值下标
            if heap_len <= r or heap[r] < heap[l]:
                # r 的值已经超出边界了，或者r对应的数小于l对应的数，则最大索引为l
                nex = l
            else:
                nex = r
            if heap[p] < heap[nex]:
                # 如果最大值大于当前根结点，则将两个节点进行互换，并更新根结点索引
                heap[p], heap[nex] = heap[nex], heap[p]
                p = nex
            else:
                # 否则退出循环
                break
        
    def build_heap(self, heap):
        # 初始化最大堆
        for i in range(len(heap) - 1, -1, -1):
            self.max_heapify(heap, i, len(heap))

    def heap_sort(self, nums):
        self.build_heap(nums)
        # 将堆顶元素与末尾元素进行交换，然后重建堆
        for i in range(len(nums) - 1, -1, -1):
            nums[i], nums[0] = nums[0], nums[i]
            # 每次元素互换后，i表示的就是剩下没有排序的数据长度，i之后的都是已经排好的
            self.max_heapify(nums, 0, i)
            
    def sortArray(self, nums: List[int]) -> List[int]:
        # 调用堆排序
        self.heap_sort(nums)
        return nums

核心方法：归并排序

• 问题：如何将两个有序列表合并成一个有序列表
  • 如何遍历一次完成合并操作
    • 两个数组已经是有序的了，那么从一个数组中向另一个数组中插入时，已经插入的位置就不会再插入了。每次插入时，只需要从上一个插入的位置开始继续向后寻找插入位置即可。
  • 在插入新数字时，原数组需要不断腾出位置，这个过程可能会增加一轮新的遍历
    • 替代方案：只要创建一个新数组，并使用两个指针来遍历原有的两个数组，不断将较小的数添加进新数组，并移动相应指针。
• 没有有序数组应该怎么办？
  • 将无序数组不断进行拆分，直到只剩下一个数字时，就可以认为这个数字就是有序的
  • 将 2 个只包含 1 个数字的有序数组合并成一个包含 2 个数字的有序数组，再将 2 个数字组成的有序数组合并成包含 4 个数字的有序数组...直到整个数组排序完成，这就是归并排序的思想
• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

class Solution:
    def merge_sort(self, nums, l, r):
        if r == l:
            return
        # 使用分治递归
        mid = (r + l) // 2
        self.merge_sort(nums, l, mid)
        self.merge_sort(nums, mid+1, r)
        i, j = l, mid+1
        tmp = []  # 创建一个临时数组，用来临时存放本次排序的结果
        while i <= mid or j <= r:
            # 这里的循环条件终止条件是，两个数组必须全部遍历完成
            if i > mid or (j <= r and nums[j] < nums[i]):
                # 当i已经遍历完成了，或者j没有遍历完，且j对应的数小于i对应的数
                tmp.append(nums[j])
                j += 1
            else:
                tmp.append(nums[i])
                i += 1
        # 将当前排好序的结果替换掉原来的数组元素
        nums[l: r+1] = tmp

    def sortArray(self, nums):
        self.merge_sort(nums, 0, len(nums)-1)
        return nums

506，相对名次，简单

核心方法：使用希尔排序。

class Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        # 初始化每个分数对应的排名（按照当前排名）
        rank = dict()
        for i, s in enumerate(score):
            rank[s] = i
        
        # 使用希尔排序
        n = len(score)
        gap = n // 2
        while gap > 0:
            for i in range(gap, n):
                curr = score[i]
                preIdx = i - gap
                while preIdx >= 0 and curr > score[preIdx]:
                    score[preIdx + gap] = score[preIdx]
                    preIdx -= gap
                score[preIdx + gap] = curr
            gap = gap // 2
		
        # i 表示当前名次，v 表示各个分数，score 为排序后的结果
        title = ("Gold Medal", "Silver Medal", "Bronze Medal")
        res = [0] * n
        for i, v in enumerate(score):
            if i < 3:
                # 前三个分别赋予奖牌名称
                res[rank[v]] = title[i]
            else:
                # 之后的赋予新名次+1
                res[rank[v]] = str(i+1)
        return res

剑指offer51，数组中的逆序对，困难

核心方法：归并排序。在合并两个递增的有序数组时，如果右边的数字比左边的小，则说明左边数组中尚未合并的数字与右边数组的这个数字都可以组成逆序对，这个逆序对数量就是左边数组当前索引到数组末尾的元素个数（因为是递增的），反之，逆序对的数量不增加。

我们指定左右递增待合并的数组的指针分别为 lPtr 和 rPtr。

我们发现用这种「算贡献」的思想在合并的过程中计算逆序对的数量的时候，只在 lPtr 右移的时候计算（也就是左指针指向元素大于右指针指向元素时），是基于这样的事实：当前 lPtr 指向的数字比 rPtr 小，但是比 R 中 [0 ... rPtr - 1] 的其他数字大，[0 ... rPtr - 1] 的其他数字本应当排在 lPtr 对应数字的左边，但是它排在了右边，所以这里就贡献了 rPtr-(mid+1) 个逆序对。

原则：谁小移动谁的指针，逆序对的个数就是右边数组中有多少个比左数组的指针对应元素小的数，所以贡献度的计算是放在移动左边指针这里的

归并排序是稳定的

时间复杂度：O(nlogn) 与归并排序相似

空间复杂度：O(n) 使用了一个临时数组

class Solution:
    def mergeSort(self, nums, tmp, l, r):
        if l >= r:
            return 0
		# 进行分治
        mid = (l + r) // 2
        inv_count = self.mergeSort(nums, tmp, l, mid) + self.mergeSort(nums, tmp, mid + 1, r)
        # 分别定义左数组指针，右数组指针，临时数组的指针，全部指向数组的头部
        i, j, pos = l, mid + 1, l
        while i <= mid and j <= r:
            if nums[i] <= nums[j]:
                tmp[pos] = nums[i]
                i += 1
                # 与归并的区别就在于这里，需要记录一次逆序对的贡献度
                inv_count += (j - (mid + 1))
            else:
                tmp[pos] = nums[j]
                j += 1
            pos += 1
        
        # 当两个指针有一个遍历完毕时，需要将另一个没遍历完的遍历完
        # 当然在遍历过程中，遍历左边数组时需要考虑计算贡献度，右边数组只需要赋值就可以了
        for k in range(i, mid + 1):
            tmp[pos] = nums[k]
            inv_count += (j - (mid + 1))  # 注意这里：贡献还是在i处完成的，并且j不动
            pos += 1
        for k in range(j, r + 1):
            tmp[pos] = nums[k]
            pos += 1
        # 将临时数组的结果赋值给原始数组
        nums[l:r+1] = tmp[l:r+1]
        return inv_count  # 返回数据合并的结果

    def reversePairs(self, nums: List[int]) -> int:
        n = len(nums)
        tmp = [0] * n  # 创建临时数组，
        # 类似归并排序
        return self.mergeSort(nums, tmp, 0, n - 1)

220，存在重复数组，中等（1438，480）

核心方法：滑动窗口，活动窗口的大小固定为k。

• 本题最大的难点在于快速地找滑动窗口内的最大值和最小值，以及删除指定元素。如果遍历求滑动窗口内的最大值和最小值，时间复杂度是 O(K)，肯定会超时。降低时间复杂度的一个绝招就是增加空间复杂度。我们的目的是快速让一组数据有序，那就寻找一个内部是有序的数据结构。

• 在 Python 中 sortedcontainers 实现了有序的容器。

  • 当频繁的插入和删除元素时，sortedcontainers 等有序的数据结构能够在在 O(log(K)) 的时间复杂度内调整 BST，从而维护结构的有序性。
  • bisect_left 找到的应该是大于等于这个值的最小值，而小于等于该值的索引是不符合的情况。因为nums[right] - t本身就是t范围内的最小值了，只要找到大于这个值，并且在窗口内的其他值，就能够找到t，k条件的情况

• 时间复杂度：$O(N*log(min(n, k)))$，每个元素遍历一次，新元素插入有序结合的调整时间复杂度为 $O(log(元素个数))$，set 中最多有 $min(n, k)$ 个元素

• 空间复杂度：O(min(n, k))

class Solution(object):
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        from sortedcontainers import SortedSet
		# 初始化有序集合
        st = SortedSet() 
        # 初始化st窗口中首尾元素索引，即左右边界
        left, right = 0, 0
        res = 0
        while right < len(nums):
            # 循环的终止条件是，窗口的右边界已经超出数组可取值范围
            if right - left > k:
                # 当窗口内的元素个数超过k个时，需要删除最左边的一个
                st.remove(nums[left])
                # 更新左边界
                left += 1
            # 针对一个元素x，期望窗口内的元素能够出现在 [x-t, x+t] 中
            # 这里的nums[right]就是x，取 nums[right] - t 这个值来判断这个值在窗口内的位置
            # 这个值是 [x-t, x+t] 范围内的最小值，如果窗口内有大于等于nums[right] - t的元素
            # （上面这个条件要满足，需要保证这个索引在窗口内，也就是0 <= index < len(st）)
            # 就说明在大小不超过k的窗口内有绝对值小于等于t的两个元素，那么就返回true
            index = bisect.bisect_left(st, nums[right] - t)
            if st and index >= 0 and index < len(st) and abs(st[index] - nums[right]) <= t:
                return True
            # 将当前节点加入窗口中，并更新右边界
            st.add(nums[right])
            right += 1
        # 遍历完毕后没有结果，就返回False
        return False

424，替换后的最长重复字符，中等

核心方法：滑动窗口。

对于最长重复子串的问题，当新加入窗口的字符为同类字符时，窗口右边界移动一位；当新加入窗口的字符为不同类字符时，窗口需要平移，也就是左右边界同时移动一位。

当能够以k次替换，将不同字符替换为相同字符时，我们还是使用这种方法。如果窗口能够扩张，说明窗口内只有一种元素，窗口内这个元素原始个数为m，那么替换k次字符后，窗口内依然只有一种元素。当窗口大小大于替换k次后的元素个数时，说明k次不足以将窗口的不同字符全部替换为相同字符，所以窗口继续左移

• 时间复杂度：O(n)，其中 n 是字符串的长度。我们至多只需要遍历该字符串一次。

• 空间复杂度：$O(|\Sigma|)$，其中 $|\Sigma|$ 是字符集的大小。我们需要存储每个大写英文字母的出现次数。

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        # 记录窗口中每个字符出现的次数
        char_map = collections.defaultdict(int)
        if not s or len(s) == 0:
            return 0
        # 记录窗口中相同字母出现次数的最大值
        history_char_max = 0
        left = 0  # 窗口的左边界
        for right in range(len(s)):
            char_map[s[right]] += 1
            # 当窗口右移过程中，只需要和新加入字符的总个数比较即可
            history_char_max = max(history_char_max, char_map[s[right]])
            if right - left + 1 > history_char_max + k:
                # 如果窗口大小 大于 出现次数最多的元素 + 替换k次别的元素
                # 说明k次替换不能使得窗口内只有一种元素，这种情况下就要移动窗口的左边界
                # 对应的字符出现次数要减1
                char_map[s[left]] -= 1
                left += 1
        return len(s) - left  # 窗口宽度

253，会议室2，中等

核心方法：堆排序

只要能在有新会议室需要时就找到一个空闲房间就行，不需要关系到底有哪些房间是空闲的；找不到空房间就新开一个。首先对所有会议开始时间进行排序，然后使用堆，将第一个房间会议的结束时间存入堆中；通过比较堆顶元素（最先完成会议的时间）和新加入会议的开始时间，来判断是否需要新开一个会议室。新开会议室需要新的会议结束时间加入堆中，如果不新开，需要先弹出堆顶元素后，再将新结束时间加入堆。处理完所有会议，堆的大小就是所开房间的总数。

时间复杂度：O(nlogn)。包含排序O(nlogn)和堆的插入，删除，堆排序O(nlogn)

空间复杂度：最坏情况下最小堆的空间为O(n)

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        # 初始化一个最小堆
        rooms = list()
        heapq.heapify(rooms)
        # 对所有会议开始时间进行排序
        intervals.sort(key = lambda x: x[0])
        # 将第一个会议结束时间添加进堆
        heapq.heappush(rooms, intervals[0][1])
        for meeting in intervals[1:]:
            if meeting[0] >= rooms[0]:
                # 新会议开始时间大于房间当前会议结束时间，就更新该房间的结束时间
                heapq.heappop(rooms)
            heapq.heappush(rooms, meeting[1])
        return len(rooms)

973，最接近原点的k个点，中等

核心方法：根据所有点到原点的距离，即坐标的平方进行排序，取前k个输出

时间复杂度：O(nlogn) 排序

空间复杂度：排序所需额外的空间复杂度为 O(\log n)

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        points.sort(key = lambda x: x[0] ** 2 + x[1] ** 2)
        return points[:k]

核心方法：堆排序

所有点到原点的距离和坐标的索引作为元素，前k个添加到最大堆，从k+1的坐标开始，大于堆顶元素的，先弹出堆顶元素，然后将这个元素加入堆中。

时间复杂度：O(nlogk)，堆排序，包括构建堆，堆插入，堆删除

空间复杂度：O(k)，堆空间的大小

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        maxHeap = [(- x ** 2 - y ** 2, i) for i, (x, y) in enumerate(points[:k])]
        heapq.heapify(maxHeap)
        
        n = len(points)
        for i in range(k, n):
            x, y = points[i]
            val = - x ** 2 - y ** 2
            if maxHeap[0][0] < val:
                heapq.heappop(maxHeap)
                heapq.heappush(maxHeap, (val, i))
        return [points[i] for (val, i) in maxHeap]

核心方法：使用快排的方法

注意：

• 在快排中，两个元素（坐标）互换的条件是横纵坐标的平方和要小于pivot的坐标平方和。
• 在递归调用时，需要判断k和i+1-left的大小关系（这一步相当于剪枝）。
  • 如果 k=i−left+1，那么说明 pivot 就是第 k 个距离最小的点，我们可以结束整个过程
  • 如果 k<i−left+1，那么说明第 k 个距离最小的点在 pivot 左侧，因此递归调用 random_select(left, i - 1, k)；
  • 如果 k>i−left+1，那么说明第 k 个距离最小的点在 pivot 右侧，因此递归调用 random_select(i + 1, right, k - (i - left + 1))。
  • 在整个过程结束之后，第 k 个距离最小的点恰好就在数组 points 中的第 k 个位置，并且其左侧的所有点的距离都小于它。 此时，我们就找到了前 k 个距离最小的点。

时间复杂度：O(n)

空间复杂度：O(logn)，递归调用的深度

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        def partition(l, r, k):
            pivot = random.randint(l, r)
            pivot_val = points[pivot][0] ** 2 + points[pivot][1] ** 2
            points[pivot], points[r] = points[r], points[pivot]
            i = l - 1
            for j in range(l, r):
                if points[j][0] ** 2 + points[j][1] ** 2 < pivot_val:
                    i += 1
                    points[i], points[j] = points[j], points[i]
            i += 1
            points[i], points[r] = points[r], points[i]

            # 归并排序
            if k < i + 1 - l:
                partition(l, i-1, k)
            elif k > i + 1 - l:
                partition(i+1, r, k-(i+1-l))
        
        n = len(points)
        partition(0, n-1, k)
        return points[:k]

207，课程表，中等

核心方法：拓扑排序

给定一个包含n个节点的有向图G，我们给出节点编号的一种排列：对于图G中的任意一条有向边(u, v)，u在排列中都出现在v的前面。那么就称这个排列就是图G的拓扑排列。

• 如果这个图是有环的，那么图G不存在拓扑结构
• 如果图 GG 是有向无环图，那么它的拓扑排序可能不止一种

将本题建模为一个拓扑排序问题

• 我们将每一门课看成一个节点；如果想要学习课程 A 之前必须完成课程 B，那么我们从 B 到 A 连接一条有向边。这样以来，在拓扑排序中，B 一定出现在 A 的前面

求出该图是否存在拓扑排序，就可以判断是否有一种符合要求的课程学习顺序。事实上，由于求出一种拓扑排序方法的最优时间复杂度为 O(n+m)，其中 n 和 m 分别是有向图 G 的节点数和边数；而判断图 G 是否存在拓扑排序，至少也要对其进行一次完整的遍历，时间复杂度也为 O(n+m)。

方法一：深度优先搜索

用一个栈来存储所有已经搜索完成的节点。

我们可以将深度优先搜索的流程与拓扑排序的求解联系起来，用一个栈来存储所有已经搜索完成的节点。

对于一个节点 uu，如果它的所有相邻节点都已经搜索完成，那么在搜索回溯到 u 的时候，u 本身也会变成一个已经搜索完成的节点。这里的「相邻节点」指的是从 u 出发通过一条有向边可以到达的所有节点。

假设我们当前搜索到了节点 u，如果它的所有相邻节点都已经搜索完成，那么这些节点都已经在栈中了，此时我们就可以把 u 入栈。可以发现，如果我们从栈顶往栈底的顺序看，由于 u 处于栈顶的位置，那么 u 出现在所有 u 的相邻节点的前面。因此对于 u 这个节点而言，它是满足拓扑排序的要求的。

• 图中任意节点在搜索时的三种状态：

  • 「未搜索」：我们还没有搜索到这个节点；
  • 「搜索中」：我们搜索过这个节点，但还没有回溯到该节点，即该节点还没有入栈，还有相邻的节点没有搜索完成（因为深度优先）；
  • 「已完成」：我们搜索过并且回溯过这个节点，即该节点已经入栈，并且所有该节点的相邻节点都出现在栈的更底部的位置，满足拓扑排序的要求。

• 算法：

  • 在每一轮的搜索搜索开始时，我们任取一个「未搜索」的节点开始进行深度优先搜索

  • 将当前搜索的节点 u 标记为「搜索中」，遍历该节点的每一个相邻节点 v

    • 如果 v 为「未搜索」，那么我们开始搜索 v，待搜索完成回溯到 u；
    • 如果 v 为「搜索中」，那么我们就找到了图中的一个环，因此是不存在拓扑排序的；
    • 如果 v 为「已完成」，那么说明 v 已经在栈中了，而 u 还不在栈中，因此 u 无论何时入栈都不会影响到 (u, v) 之前的拓扑关系，以及不用进行任何操作。

  • 当 u 的所有相邻节点都为「已完成」时，我们将 u 放入栈中，并将其标记为「已完成」

• 优化：

  • 由于我们只需要判断是否存在一种拓扑排序，而栈的作用仅仅是存放最终的拓扑排序结果，因此我们可以只记录每个节点的状态，而省去对应的栈。

时间复杂度：O(n+m)，其中 n 为课程数，m 为先修课程的要求数。这其实就是对图进行深度优先搜索的时间复杂度。

空间复杂度: O(n+m)。题目中是以列表形式给出的先修课程关系，为了对图进行深度优先搜索，我们需要存储成邻接表的形式，空间复杂度为 O(n+m)。在深度优先搜索的过程中，我们需要最多 O(n) 的栈空间（递归）进行深度优先搜索，因此总空间复杂度为 O(n+m)。

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
		# 记录每条边，其中key为排在前面的课程序号，也就是必须先修的课程，值为列表，存放后修的课
        edge = collections.defaultdict(list)
        for info in prerequisites:
            edge[info[1]].append(info[0])
            
        # 使用长度为课程总数的列表，用来记录每个节点的状态，替代栈
        visited = [0] * numCourses  # 0 表示【未搜索】
        # 返回的结果：是否存在一种拓扑关系
        valid = True
        
        def dfs(u):
            # 使用深度优先
            nonlocal valid  # 将【是否拓扑结果】转化为内部变量
            visited[u] = 1  # 1 表示【搜索中】
            for v in edge[u]:
                # 查询当前修u前必修的其他课程v
                if visited[v] == 0:
                    # 如果其他课程v还没有被搜索，那么就对其进行搜索
                    dfs(v)
                    if not valid:
                        # 如果 valid
                        return
                elif visited[v] == 1:
                    valid = False
                    return 
                # 如果当前节点已经是【已完成】那么直接跳过就行
            # u 出来的有向边全部遍历完毕，u 就是已完成
            visited[u] = 2
        
        for i in range(numCourses):
            if valid and not visited[i]:
                # 当前课程没有被访问过，且截至目前还能够位置拓扑排序
                dfs(i)
            
        return valid

核心方法：顺序生成拓扑结构，即使用广度优先遍历 推荐

考虑拓扑排序中最前面的节点，该节点一定不会有任何入边，也就是它没有任何的先修课程要求。当我们将一个节点加入答案中后，我们就可以移除它的所有出边，代表着它的相邻节点少了一门先修课程的要求。如果某个相邻节点变成了「没有任何入边的节点」，那么就代表着这门课可以开始学习了。按照这样的流程，我们不断地将没有入边的节点加入答案，直到答案中包含所有的节点（得到了一种拓扑排序）或者不存在没有入边的节点（图中包含环）。

• 算法：

  我们使用一个队列来进行广度优先搜索。初始时，所有入度为 0 的节点都被放入队列中，它们就是可以作为拓扑排序最前面的节点，并且它们之间的相对顺序是无关紧要的。

  在广度优先搜索的每一步中，我们取出队首的节点 u：

  • 我们将 u 放入答案中；
  • 我们移除 u 的所有出边，也就是将 u 的所有相邻节点的入度减少 1。如果某个相邻节点 v 的入度变为 0，那么我们就将 v 放入队列中。

  在广度优先搜索的过程结束后。如果答案中包含了这 n 个节点，那么我们就找到了一种拓扑排序，否则说明图中存在环，也就不存在拓扑排序了。

• 优化

  省去存放答案数组，而是只用一个变量记录被放入答案数组的节点个数。在广度优先搜索结束之后，我们判断该变量的值是否等于课程数，就能知道是否存在一种拓扑排序。

时间复杂度：O(n+m)，其中 n 为课程数，m 为先修课程的要求数。

空间复杂度：O(n+m)。题目中是以列表形式给出的先修课程关系，为了对图进行广度优先搜索，我们需要存储成邻接表的形式，空间复杂度为 O(n+m)。在广度优先搜索的过程中，我们需要最多 O(n) 的队列空间（迭代）进行广度优先搜索。因此总空间复杂度为 O(n+m)。

class Solution:
   	def canFinish(self, numsCourses, prerequisites):
        edges = collections.defaultdict(list)
        # 记录每个节点的入度
        indeg = [0] * numsCourses
        
        for info in prerequisites:
       		edges[info[1]].append(info[0])
            indeg[info[0]] += 1  # 记录每个节点入度
        
        # 记录初始值中入度为零的节点，放入队列
        q = collections.deque([u for u in range(numsCourses) if indeg[u] == 0])
        visited = 0  # 使用一个变量来记录访问过的节点数
        
        while q:
           	u = q.popleft()
            # 访问过的节点数+1
            visited += 1
            for v in edges[u]:
                # 相邻点的入度减1
                indeg[v] -= 1
                if indeg[v] == 0:
                    # 如果当前节点的入度值为0，那么将其加入队列
                    q.append(v)
		return visited == numsCourses

210，课程表2，中等

核心方法：主要采用了广度优先搜索，代码参考209课程表中的代码。209中问的是能不能找到一种拓扑排序，而本题要求将这个拓扑排序返回，所以要修改的部分就是创建一个列表，访问过的节点（课程编号）加入列表中，如果最后访问过的节点数量等于课程总数，那么就返回这个结果列表；否则返回一个空列表

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

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

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        edges = collections.defaultdict(list)
        indeg = [0] * numCourses
        res = list()
        
        for info in prerequisites:
            edges[info[1]].append(info[0])
            indeg[info[0]] += 1
        
        q = collections.deque([u for u in range(numCourses) if indeg[u] == 0])
        visited = 0

        while q:
            u = q.popleft()
            res.append(u)
            visited += 1
            for v in edges[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    q.append(v)
        return res if visited == numCourses else []

581，最短无序连续子数组，中等

核心方法：可以先对数组进行排序，然后比较两个数组对应位置第一个不相等的头和尾，索引之间就是最短子数组的长度。

时间复杂度：O(nlogn)，排序

空间复杂度：O(n)，复制了一份原来的数组

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        new_nums = nums[:]
        new_nums.sort()
        # 这里指定start为列表长度，end为0的目的是分别求最小和最大
        start, end = len(new_nums), 0
        for i in range(len(nums)):
            if new_nums[i] != nums[i]:
                start = min(start, i)
                end = max(end, i)
        return end - start + 1 if start < end else 0

核心方法：栈

遍历数组，如果元素一直都是升序的，那么将这些元素的下标存入栈，因为这些元素的顺序都是正确的；如果发现遍历到的数字比栈顶元素小，说明这个位置不正确，那么我们将栈顶元素不断弹出，直到栈顶元素比当前遍历的数小，如果栈顶元素的下标为k，那么这个元素的正确位置应该为k+1，这样就能够找到左边界。同样的方法去寻找右边界。

时间复杂度：O(n)

空间复杂度：O(n)

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        l, r = len(nums), 0
        
        stack = list()
        for i in range(n):
            while stack and nums[stack[-1]] > nums[i]:
                l = min(l, stack.pop())
            stack.append(i)

        stack = list()
        for i in range(n-1, -1, -1):
            while stack and nums[stack[-1]] < nums[i]:
                r = max(r, stack.pop())
            stack.append(i)

        return r - l + 1 if r > l else 0    

核心方法：不使用额外空间

• 第一次遍历：从前向后遍历，需要找到第一个不是生序的位置，记录最小元素；从后向前遍历，找到第一个不是降序的位置，记录最大元素
• 第二次遍历： 从前向后遍历，找到第一个大于最小元素的位置；从后向前遍历，找到第一个小于最大元素的位置，这两个位置之间就是最短无序子数组

时间复杂度：O(n)

空间复杂度：O(1)

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        min_v, max_v = float('inf'), float('-inf')
        # 找到最小值
        for i in range(1, n):
            if nums[i] < nums[i-1]:
                min_v = min(min_v, nums[i])
		# 找到最大值
        for i in range(n-2, -1, -1):
            if nums[i] > nums[i+1]:
                max_v = max(max_v, nums[i])
        # 正序遍历，找到第一个大于最小值的位置
        for l in range(n):
            if nums[l] > min_v:
                break
        # 逆序遍历，找到第一个小于最大值的位置
        for r in range(n-1, -1, -1):
            if nums[r] < max_v:
                break
        return r - l + 1 if r > l else 0