Leetcode刷题笔记——排序算法篇

前言:十大经典排序算法

1. 冒泡排序 【本文不涉及】
2. 选择排序 【本文不涉及】
3. 插入排序 【了解即可】
4. 希尔排序 【本文不涉及】
5. 归并排序 【重点掌握】
6. 快速排序 【重点掌握】
7. 堆排序 【重点掌握】
8. 桶排序 【了解即可】
9. 计数排序 【需熟悉】
10. 基数排序 【本文不涉及】

一、自定义排序规则案例演示

第一题：按照频率将数组升序排序

Leetcode1636. 按照频率将数组升序排序：简单题 （详情点击链接见原题）

给你一个整数数组 nums ，请你将数组按照每个值的频率 升序 排序。如果有多个值的频率相同，请你按照数值本身将它们 降序 排序

解题思路

1. 先使用哈希表进行词频统计
2. 再以二元组(x, cnt)的形式转存到数组list中【x为对应的nums中的数值，cnt为x在nums中出现的频次】
3. 以 cnt 为第一关键字进行升序排序,以x的大小为第二关键字进行降序排序

python代码解法:

from collections import Counter


class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        count = Counter(nums)  # 1.对每个数以及该数出现的频率进行统计
        count = list(count.items())  # 2.将数与频率转换为列表
        count = sorted(count, key=lambda x: (x[1], -x[0]))  # 3.以频率为第一关键字进行升序排序,以数字大小为第二关键字进行降序排序
        res = []  
        for li in count:
            for _ in range(li[1]):
                res.append(li[0])  # 4.统计结果
        return res

第二题：通过投票对团队排名

Leetcode1366. 通过投票对团队排名：中等题 （详情点击链接见原题）

现在有一个特殊的排名系统，依据参赛团队在投票人心中的次序进行排名，每个投票者都需要按从高到低的顺序对参与排名的所有团队进行排位。

方法1：利用哈希表
设参与排名的人数为n，（即数组votes中任一字符串的长度），利用哈希表，
key: 键为一个参与排名的人，
value: 值为一个长度为n的数组rank，rank[i]表示这个人排名为i的次数

1. 遍历 votes 中的每一个字符串并进行统计，就可以得到上述存储了每一个人排名情况的哈希映射
2. 在 rank 相等的情况下，我们需要以 vid为第二关键字进行升序排序（可以将vid从字符转换成对应的ASCII，并用其相反数进行升序排序）

python代码解法1:

class Solution:
    def rankTeams(self, votes: List[str]) -> str:
        n = len(votes[0])
        hash_map = {}
        for vote in votes:
            for k, v in enumerate(vote):
                hash_map[v] = hash_map.get(v, [0] * n)
                hash_map[v][k] += 1
        rank_list = list(hash_map.items())
        rank_list = sorted(rank_list, key=lambda x: (x[1], -ord(x[0])), reverse=True)
        return "".join(x[0] for x in rank_list)

方法2：利用二维数组代替哈希
4. dw[26][27]的含义：26的含义为参赛队伍可能有26支，dw[i]是一个大小为 27 的一维数组，记录该队伍在每个排名下的频次

• dw[0][0]=5 表示 A 队伍取得了 5 票排位第一
• dw[1][1] = 2表示B队伍取得了2票排位第二，dw[1][2]=3表示B队伍取得了3票排位第三
• dw[2][1] = 3表示C队伍取得了3票排位第二，dw[2][2]=2表示C队伍取得了2票排位第三

5. 如果两个队伍考虑完所有投票情况后仍然出现并列现象，则根据团队字母的字母顺序进行排名，所以我们用最后一位保存字母的ASCII码
6. 在排二维数组的时候，首先对比二维数组中第一个数的大小，如果相同就去比较第二个，第三个，按降序排序，如果排名相同则按第二个关键字，队伍的字母顺序升序排序【按队伍的ASCII码取负值按降序排序即升序：负负得正】

python代码解法2:

class Solution:
    def rankTeams(self, votes: List[str]) -> str:
        dw = [[0] * 27 for _ in range(26)]
        res = ""
        for vote in votes:
            for i in range(len(vote)):
                dw[ord(vote[i]) - ord('A')][i] += 1   # 1.记录每个队伍的排名信息
                dw[ord(vote[i]) - ord('A')][-1] = (ord(vote[i]) - ord('A')) + 1  # 2.用最后一位记录该队伍信息

        dw = sorted(dw, key=lambda x: (x[:-1], -x[-1]), reverse=True)  # 3.根据排名情况按降序排序,如果排名相同，根据字母大小的相反数按降序排序(保证A和B排名一致的情况下,A仍然在B的前面)

        for i in range(0, len(dw)):  # 4.统计按要求排完后的队伍
            if dw[i][-1] != 0:
                res += chr(dw[i][-1] + ord('A') - 1)
        return res

第三题：根据字符串出现频率排序

Leetcode451：根据字符串出现频率排序：中等题 （详情点击链接见原题）

给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数

python代码解法:利用二维数组代替哈希

class Solution:
    def frequencySort(self, s: str) -> str:
        char_map = [[0 for _ in range(2)] for _ in range(128)]
        for i in s:
            char_map[ord(i)][0] = ord(i)  # 1.记录该字符对应的 ASCII 码
            char_map[ord(i)][1] += 1    # 2.记录该字符出现的频次
        char_map = sorted(char_map, key=lambda x: x[1], reverse=True)  # 3.按照频次进行降序排序
        res = ''
        for ch in char_map:
            if ch[1] > 0:
                res += chr(ch[0]) * ch[1]  # 4.将字符以及该字符出现的频次记录到结果集中
        return res

第四题：最大数

Leetcode179. 最大数：中等题 （详情点击链接见原题）

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

python代码解法1: 类似于冒泡排序

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        n = len(nums)
        nums = list(map(str, nums))
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] < nums[j] + nums[i]:
                    nums[i], nums[j] = nums[j], nums[i]
        return str(int(''.join(nums)))

python代码解法2: 自定义排序规则

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        def sort_rule(x, y):
            if x + y < y + x:
                return 1
            else:
                return -1
        nums = list(map(str, nums))
        nums.sort(key=cmp_to_key(sort_rule))
        # print(nums)
        return str(int(''.join(nums)))

二、计数排序经典案例

第一题:自定义字符串排序

Leetcode791：自定义字符串排序：中等题 （详情点击链接见原题）

给定两个字符串 order 和 s 。order 的所有字母都是 唯一 的，并且以前按照一些自定义的顺序排序

python代码解法

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        counts = [0] * 26
        ans = ''
        for i in s:   # 1.遍历s进行字符出现的频率统计
            counts[ord(i) - ord('a')] += 1
        for o in order:    # 遍历order字符串
            num = ord(o) - ord('a')  
            if counts[num] >= 0:
                ans += o * counts[num]  # 2.按照order中出现的字符的顺序，逐个乘以字符出现的频率追加到ans末尾
                counts[num] = 0    # 3.添加到结果集后将对应字符出现频率置为0

        for i in range(0, len(counts)):  # 4.遍历count将s中的多余字符追加到ans的末尾
            if counts[i] != 0:
                ans += chr(ord('a') + i) * counts[i]
        return ans

第二题：数组的相对排序

Leetcode1122. 数组的相对排序：简单题 （详情点击链接见原题）

给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中,对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾

1 <= arr1.length, arr2.length <= 1000题目条件中有前提条件

1. 所以申请一个大小为 1001 的 count 数组
2. 以 arr1 数组中数字的大小为索引，值为该数字出现的频率记录到数组 count 中
3. 然后遍历 arr2 的同时，将 arr2 中的数置入 arr1中，注意 count 中的频率
4. 处理好 arr2 之后，再处理剩下的数字，按照 count数组中所记录的位置信息和频率信息追加到arr1数组的末尾

python代码解法(一维数组代替哈希映射)

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        count = [0] * 1001   # 1.申请一个大小为 1001 的 count 数组
        for i in arr1:    # 2.以 arr1 数组中数字的大小为索引，值为该数字出现的频率
            count[i] += 1

        n = 0
        for i in arr2:  # 3.遍历 arr2 数组,按 arr2 中的顺序直接在 arr1 的基础上进行排序
            while n < len(arr1) and count[i] > 0:
                arr1[n] = i  
                count[i] -= 1
                n += 1

        for index in range(len(count)):   # 4.遍历count数组中不为0的位置和该位置数字出现的频率
            while n < len(arr1) and count[index] > 0:
                arr1[n] = index		# 5.追加到 arr1 的末尾
                count[index] -= 1
                n += 1
        return arr1

python代码解法(利用哈希表)

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        hash_map = Counter(arr1)
        print(hash_map)
        ans = []
        for i in arr2:
            for j in range(hash_map[i]):
                ans.append(i)
            hash_map.pop(i)
        hash_list = list(hash_map.items())
        hash_list.sort()
        for item in hash_list:
            for i in range(item[1]):
                ans.append(item[0])
        return ans

第三题：最小时间差

Leetcode539. 最小时间差：中等题 （详情点击链接见原题）

给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示

解题思路：我们需要找出时钟盘中夹角最小的两个时间点，其中包括分布在 00:00左右两侧（横跨了一天）的时间点
因此一个简单的方式是对于每个timePointes[i]，我们不仅记录【当天该时间点对应的偏移量】，还记录【下一天该时间点】对应的偏移量

python代码解法

class Solution:
    def findMinDifference(self, timePoints: List[str]) -> int:
        n = len(timePoints) * 2
        nums = [0] * n
        index = 0
        for time in timePoints:
            hour, minute = int(time[:2]), int(time[-2:])
            nums[index] = hour * 60 + minute
            nums[index + 1] = nums[index] + 1440
            index += 2
        nums.sort()
        min_gap = float('inf')
        for i in range(n - 1):
            min_gap = min(min_gap, nums[i + 1] - nums[i])
        return min_gap

第四题：使数组唯一的最小增量

Leetcode945. 使数组唯一的最小增量：中等题 （详情点击链接见原题）

给你一个整数数组 nums 。每次 move 操作将会选择任意一个满足 0 <= i < nums.length 的下标 i，并将 nums[i] 递增 1

解题思路：首先将数组进行排序，然后从左到右遍历数组

• 如果当前元素大于上一个元素，continue
• 如果当前元素小于等于上一个元素，就需要增加当前元素直到大于上一个元素

python代码解法

class Solution:
    def minIncrementForUnique(self, nums: List[int]) -> int:
        nums.sort()
        ans = 0
        for i in range(1, len(nums)):
            if nums[i] <= nums[i - 1]:
                ans += (nums[i - 1] - nums[i] + 1)
                nums[i] = nums[i - 1] + 1
        return ans

第五题：H指数

Leetcode274. H 指数：中等题 （详情点击链接见原题）

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数

解题思路
设 n 为 citations 的长度，h 不可能超过 n，对于引用次数大于 n 的论文，我们在统计的时候可以看成是引用次数等于 n 的论文
创建一个长度为 n + 1 的数组【因为最少的引用次数为 0 次，最大的引用次数大于 n 时取n】
cnt[i]：引用次数为 i 的论文的数量为 cnt[i]
为了快速算出有多少论文的引用次数 ≥ i，每次循环把 cnt[i] 加到 s 种，只要 s >= i 成立，此时的 i 就是满足 s >= i 的最大的 i，直接返回 i 作为答案

python代码解法

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        counts = [0] * (n + 1)
        for c in citations:
            counts[min(c, n)] += 1  # 引用次数 > n,等价于引用次数为 n
        s = 0
        for i in range(n, -1, -1):  # i = 0 的时候,s >= i一定成立
            s += counts[i]
            if s >= i:  # 说明至少有 i 篇论文的引用次数至少为i
                return i

三、快速排序案例演示

第一题：排序数组

Leetcode912. 排序数组：中等题 （详情点击链接见原题）

给你一个整数数组 nums，请你将该数组升序排列

每种排序算法都可以实现数组的升序和降序排序，其中涉及的时间复杂度这里不做过多介绍，博主在本文中根据每道题的侧重点不同分别讲一种排序算法

快速排序使用分治法（Divide and Conquer）策略来把一个序列分为较小和较大的2 个子序列，然后递归的排序两个子序列

基本步骤

1. 挑选基准值：从数列中挑出一个元素称为"基准 (pivot)"
2. 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面，【与基准值相等的数可以放到任何一边】，分割结束后对基准值的排序就已经完成
3. 递归排序子序列：递归地将小于基准值元素的子序列和大于基准元素的子序列排序

python代码解法（优化前）:

class Solution:
    def partition(self, nums, low, high):
        pivot = nums[low]
        while low < high:
            while low < high and nums[high] >= pivot:  # 当nums[right]==pivot的时候
                high -= 1
            nums[low] = nums[high]
            while low < high and nums[low] < pivot:
                low += 1
            nums[high] = nums[low]
        nums[low] = pivot
        return low

    def quick_sort(self, nums, l, h):
        if l < h:
            point = self.partition(nums, l, h)
            self.quick_sort(nums, l, point - 1)
            self.quick_sort(nums, point + 1, h)

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

选取基准值pivot也有多种方式，且选取pivot的方法对排序的时间性能有着决定性的影响，例如对于一个逆序数组，如果每次选取数组中的第一个元素为pivot，那么将其正序排列的过程将会变得非常慢
如果没有针对特殊测试用例：针对顺序数组或者逆序数组，一定要随机化选择切分元素(pivot)，否则在输入数组基本有序或者逆序的时候，快速排序会变得非常慢

python代码解法（优化后-随机选择partition）:

import random


class Solution:
    def partition(self, nums, low, high):
        pivot = nums[low]
        while low < high:
            while low < high and nums[high] >= pivot:  # 当nums[right]==pivot的时候
                high -= 1
            nums[low] = nums[high]
            while low < high and nums[low] < pivot:
                low += 1
            nums[high] = nums[low]
        nums[low] = pivot
        return low

    def randomPartition(self, arr, low, high):
        pivot_idx = random.randint(low, high)
        arr[low], arr[pivot_idx] = arr[pivot_idx], arr[low]
        return self.partition(arr, low, high)

    def quick_sort(self, nums, l, h):
        if l < h:
            mid = self.randomPartition(nums, l, h)  # 以mid为分割点【随机选择pivot】
            self.quick_sort(nums, l, mid - 1)
            self.quick_sort(nums, mid + 1, h)

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

第二题：颜色分类

Leetcode75. 颜色分类：中等题 （详情点击链接见原题）

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

p0的值初始化为 0，p2的初始值为n - 1，在遍历的过程中，我们需要找出所有的 0 交换到数组头部，找出所有的 2 交换至数组尾部
由于此时其中一个指针 p2 是从右向左移动的，因此当我们在从左向右遍历整个数组时，如果遍历到的位置超过了 p2 ，那么就可以直接停止遍历了

python代码解法:

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """

        n = len(nums)
        p0, p2 = 0, n - 1
        i = 0
        while i <= p2:  # i指针从左往右扫描
            while i <= p2 and nums[i] == 2:  # case:i扫描的过程中如果nums[i]=2,不断将其与nums[p2]进行交换直到新的nums[i]不为2,如果i指向的位置大于p2直接停止遍历
                nums[i], nums[p2] = nums[p2], nums[i]
                p2 -= 1
            if nums[i] == 0:  # case:i扫描的过程中如果nums[i]=0,将其与nums[p0]进行交换，并将p0向后移动一个位置
                nums[i], nums[p0] = nums[p0], nums[i]
                p0 += 1
            i += 1

四、堆排序经典案例

前文中只字未提的堆排序在TopK问题中可以发挥它真正的威力，所以我们在下面的几道题中仔细看看堆排序的底层实现原理
堆排序 Heapsort 是指利用堆 heap 这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点

对于一个待排序的包含 n 个元素的数组 nums，堆排序的步骤如下

1. 建堆：将待排序的数组初始化为大根堆（小根堆）堆顶元素 即 根节点即为整个数组中的最大值（最小值）
2. 交换和调整：将堆顶元素与末尾元素进行交换，此时末尾元素即为最大值（最小值），除去末尾元素后，继续对剩余 n-1个元素重新构造成一个大根堆（小根堆），如此便可得到原数组 n 个元素中的次大值（次小值）
3. 重复步骤2：直到堆中仅剩一个元素，如此便可得到一个有序序列

4.1 第K大问题

第一题：第三大的数

Leetcode414. 第三大的数：中等题 （详情点击链接见原题）

给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数

python代码解法:

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        def max_heapify(heap, parent, heap_size):
            child = 2 * parent + 1
            while child < heap_size:
                if child + 1 < heap_size and heap[child + 1] > heap[child]:
                    child = child + 1
                if heap[child] > heap[parent]:
                    heap[child], heap[parent] = heap[parent], heap[child]
                    parent = child
                    child = 2 * parent + 1
                else:
                    break
        nums = list(set(nums))	# 1.利用set()方法过滤掉重复元素
        n = len(nums)
        for i in range((n - 1) // 2, -1, -1):  # 2.将题目所给的nums数组调整为一个最大堆
            max_heapify(nums, i, n)

        if len(nums) >= 3:   # 3.如果nums的规模大于等于3
            for i in range(n - 1, n - 4, -1):
                nums[0], nums[i] = nums[i], nums[0]  # 4.将堆顶元素与末尾元素互换
                max_heapify(nums, 0, i)     # 5.堆的规模－1，从堆顶开始将剩余元素重新调整为一个最大堆
            return nums[-3]  # 6.1 返回第三大的元素
        else:
            return nums[0]   # 6.2 返回最大的堆顶元素

第二题：数组中的第K个最大元素

Leetcode215：数组中的第K个最大元素：中等题 （详情点击链接见原题）

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素

python代码解法:

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def max_heapify(heap, parent, heap_size):
            child = 2 * parent + 1
            while child < heap_size:
                if child + 1 < heap_size and heap[child + 1] > heap[child]:
                    child = child + 1
                if heap[child] > heap[parent]:
                    heap[child], heap[parent] = heap[parent], heap[child]
                    parent = child
                    child = 2 * parent + 1
                else:
                    break

        n = len(nums)
        for i in range((n - 1) // 2, -1, -1):  # 1.从第一个非叶子节点开始调整为最大堆
            max_heapify(nums, i, n)

        for i in range(n - 1, n - k - 1, -1):
            nums[0], nums[i] = nums[i], nums[0]  # 2.将堆顶元素与末尾元素互换
            max_heapify(nums, 0, i)   # 3.堆的规模－1，从堆顶开始将剩余元素重新调整为一个最大堆
        return nums[-k]

4.2 TopK大 or TopK小

在TopK问题中，和堆排序有点区别，因为在 TopK问题中，涉及到维护一个规模为 K 的最大堆最小堆的问题，这就没有现成的数组让我们建堆，
TOPK 问题解题步骤

1. 我们需要从无到有通过堆插入的方式建立规模为 K 的大根堆或者小根堆
2. 遍历数组中的剩余元素，和堆顶元素互换，通过对堆顶元素的下沉操作维护堆的规模始终为K
3. 保证数组遍历完后堆中的元素刚好是数组中的 TOPK 大或者 TOPK 小的元素

第一题：前 K 个高频元素

Leetcode347. 前 K 个高频元素：中等题 （详情点击链接见原题）

给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案

解题思路

1. 遍历统计元素出现的频率cnt，转换为 list
2. 利用前k个数构造规模为k的最小堆min_heap
3. 遍历cnt 中剩余的数据，大于堆顶则入堆，对堆顶节点进行下沉操作维护规模为k的最小堆
4. 遍历完 cnt 后遍历 min_heap，提取min_heap中的键

python代码解法:

class Solution:
    def sift_up(self, heap):
        child_index = len(heap) - 1
        temp = heap[child_index]
        parent_index = (child_index - 1) // 2
        while parent_index >= 0 and temp[1] < heap[parent_index][1]:
            heap[child_index] = heap[parent_index]
            child_index = parent_index
            parent_index = (child_index - 1) // 2
        heap[child_index] = temp

    def sift_down(self, heap, parent_index, heap_size):
        temp = heap[parent_index]
        child_index = 2 * parent_index + 1
        while child_index < heap_size:
            if child_index + 1 < heap_size and heap[child_index][1] > heap[child_index + 1][1]:
                child_index = child_index + 1
            if heap[child_index][1] < temp[1]:
                heap[parent_index] = heap[child_index]
                parent_index = child_index
                child_index = 2 * parent_index + 1
            else:
                break
        heap[parent_index] = temp

    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt = Counter(nums)
        cnt = list(cnt.items())
        min_heap = []
        for i in range(k):
            min_heap.append(cnt[i])
            self.sift_up(min_heap)

        for i in range(k, len(cnt)):
            if cnt[i][1] > min_heap[0][1]:
                min_heap[0] = cnt[i]
                self.sift_down(min_heap, 0, k)
        return [item[0] for item in min_heap]

第二题： 前K个高频单词

Leetcode692. 前K个高频单词：中等题 （详情点击链接见原题）

给定一个单词列表 words 和一个整数 k，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序

python代码解法:

import heapq
from typing import List
from collections import Counter


class Word:
    def __init__(self, key, value):
        self.key = key
        self.value = value

    def __lt__(self, other):
        if self.value != other.value:
            return self.value < other.value
        return self.key > other.key  # 从小到大


class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        cnt = Counter(words)
        hp = []
        for key, value in cnt.items():
            heapq.heappush(hp, Word(key, value))
            while len(hp) > k:
                heapq.heappop(hp)
        hp.sort(reverse=True)
        return [x.key for x in hp]

第三题：数据流中的第 K 大元素

Leetcode703. 数据流中的第 K 大元素：中等题 （详情点击链接见原题）

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素

解题思路

1. 使用大小为 K 的小根堆，在初始化的时候，保证堆中的元素个数不超过K
2. 在每次add()的时候，将新元素 push() 到堆中，如果此时堆中元素超过了K，那么需要把堆中的最小元素pop()出来
3. 此时堆中的最小元素（堆顶）就是整个数据流中的第 K 大元素

关于heapq模块的使用大家可以参考Python heapq库的用法介绍，实际的面试中，大家最好不要用模块和方法实际操作，其实heapq底层的原理就是构建/维护一个最大堆/最小堆的操作，即排序算法中堆排序的底层实现，这里只是介绍另一种实现方法，大家如果对堆的相关操作感兴趣的话可以先手写堆排序(当你了解底层原理后再使用这个模块)

heappush(heap, num): 先创建一个空堆，然后将数据一个一个地添加到堆中。每添加一个数据后，heap都满足小顶堆的特性，对应堆的插入操作【节点上浮】
heapify(array):直接将数据列表调整成一个小顶堆
heappop(heap): 将堆顶的数据出堆，并将堆中剩余的数据构造成新的小顶堆，对应堆的删除操作【节点下沉】
python代码解法1:调用python库函数heapq

import heapq

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.heap = nums
        heapq.heapify(self.heap)  # 1.将题目所给nums初始化为一个小根堆

    def add(self, val: int) -> int:
        heapq.heappush(self.heap, val)  # 2.在堆中添加元素并维持小根堆的特性
        while len(self.heap) > self.k:
            heapq.heappop(self.heap)   # 3.堆尾元素与堆顶元素互换,互换后将堆尾元素pop,对堆顶节点进行下沉操作重新维护一个最小堆
        return self.heap[0]

python代码解法2:手动实现堆的底层代码（困难做法）

class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.heap = nums
        for i in range(len(self.heap) // 2 - 1, -1, -1):  # 1.从第一个非叶子节点开始调整为最小堆
            self.min_heapify(self.heap, i, len(self.heap))

    def min_heapify(self, heap, parent, heap_size):   # 调整为最小堆的函数
        child = 2 * parent + 1
        while child < heap_size:
            if child + 1 < heap_size and heap[child + 1] < heap[child]:
                child = child + 1
            if heap[child] < heap[parent]:
                heap[child], heap[parent] = heap[parent], heap[child]
                parent = child
                child = 2 * parent + 1
            else:
                break

    def sift_up(self, min_heap):    # 在堆的末尾插入节点的上浮操作
        child_index = len(min_heap) - 1
        parent_index = (child_index - 1) // 2
        temp = min_heap[child_index]
        while child_index > 0 and temp < min_heap[parent_index]:
            min_heap[child_index] = min_heap[parent_index]
            child_index = parent_index
            parent_index = (child_index - 1) // 2
        min_heap[child_index] = temp

    def sift_down(self, min_heap, parent_index, heap_size):  # 针对于堆顶节点的下沉操作
        temp = min_heap[0]
        child_index = 2 * parent_index + 1
        while child_index < heap_size:
            if child_index + 1 < heap_size and min_heap[child_index + 1] < min_heap[child_index]:
                child_index += 1
            if temp > min_heap[child_index]:
                min_heap[parent_index] = min_heap[child_index]
                parent_index = child_index
                child_index = 2 * parent_index + 1
            else:
                break
        min_heap[parent_index] = temp

    def add(self, val: int) -> int:
        self.heap.append(val)
        self.sift_up(self.heap)
        n = len(self.heap)
        while n > self.k:
            self.heap[0] = self.heap[-1]
            self.heap.pop()
            self.sift_down(self.heap, 0, n - 1)
            n -= 1
        return self.heap[0]

五、插入排序案例演示

第一题：对链表进行插入排序

Leetcode147. 对链表进行插入排序：中等题 （详情点击链接见原题）

给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头

1. 先找到待插入的结点（前一个结点值比当前的大）移除，移除前保存
2. 将该结点插入到合适的位置，从头遍历比较，并插入

python代码解法:

class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy_head = ListNode()
        dummy_head.next = head
        cur = head
        while cur and cur.next:
            if cur.val <= cur.next.val:
                cur = cur.next
            else:
                temp = cur.next  # 保存节点
                cur.next = cur.next.next  # 删除节点

                prev = dummy_head
                while prev.next.val <= temp.val:
                    prev = prev.next
                temp.next = prev.next
                prev.next = temp
        return dummy_head.next

六、归并排序经典案例

第一题：合并两个有序数组

Leetcode88. 合并两个有序数组：简单题 （详情点击链接见原题）

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目

python代码解法:

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        p1, p2 = m - 1, n - 1  # 创建两个指针分别指向nums1和nums2的第一个位置
        k = m + n - 1
        while p1 >= 0 and p2 >= 0:
            if nums1[p1] > nums2[p2]:
                nums1[k] = nums1[p1]
                p1 -= 1
            else:
                nums1[k] = nums2[p2]
                p2 -= 1
            k -= 1
        while p2 >= 0:
            nums1[k] = nums2[p2]
            p2 -= 1
            k -= 1

第二题：合并两个有序链表

Leetcode21. 合并两个有序链表：简单题 （详情点击链接见原题）

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

python代码解法:

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy_head = p = ListNode()  # 创建一个虚拟头结点dummy_head用于返回链表,p指针用来扫描
        l1, l2 = list1, list2  # l1和l2分别指向list1和list2的头结点
        while l1 and l2:
            if l1.val < l2.val:
                p.next = l1
                l1 = l1.next
            else:
                p.next = l2
                l2 = l2.next
            p = p.next
        p.next = l1 if l1 else l2
        return dummy_head.next

第三题：合并 K 个升序链表

Leetcode23. 合并 K 个升序链表：困难题 （详情点击链接见原题）

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表

python代码解法:

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        dummy_head = ListNode()    # 1.创建一个虚拟头结点用于返回最终结果
        for li in lists:     # 2.按照合并两个有序链表的思路逐个对列表中的链表进行合并
            cur_node = dummy_head    # 3.cur_node指针重新指向合并后的链表的起始位置
            p1, p2 = cur_node.next, li
            while p1 and p2:
                if p1.val < p2.val:
                    cur_node.next = p1
                    p1 = p1.next
                else:
                    cur_node.next = p2
                    p2 = p2.next
                cur_node = cur_node.next
            cur_node.next = p1 if p1 else p2  # 4.如果其中某个链表提前遍历完毕,将剩余链表直接挂在后面
        return dummy_head.next

第四题: 排序链表

Leetcode148. 排序链表：中等题 （详情点击链接见原题）

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

分割cut环节：
找到当前链表中点，并从中点将链表断开

• 我们使用fast, slow快慢指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点
• 找到中点slow后，执行slow.next=None将链表切断
• 递归分割时，输入当前链表左端点head和中心节点slow的下一个节点tmp（因为链表是从slow切断的）
• cut递归终止条件：当 head.next==None说明只有一个节点，直接返回此节点

合并 merge 环节:
将两个排序链表合并，转换为一个有序链表

1. 双指针合并，建立辅助 ListNode h 作为头部
2. 设置两指针 left, right 分别指向两链表的头部，比较两指针处节点值大小，由小到大加入合并链表头部，指针交替前进直至添加完两个链表
3. 返回辅助ListNode h作为头部的下一个节点 h.next
4. 时间复杂度O(l + r)，l, r 分别代表两个链表长度

python代码解法:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:  # 1.递归出口
            return head

        # cut the LinkedList at the mid index.
        slow, fast = head, head.next
        while fast and fast.next:    # 2.慢指针每走一步,快指针往前走两步,循环找到中间节点
            fast, slow = fast.next.next, slow.next
        mid, slow.next = slow.next, None   # 3.从中间节点处切断.
        # recursive for cutting.
        left, right = self.sortList(head), self.sortList(mid)
        h = res = ListNode(0)   # 4.合并了两个有序链表的操作(即上面的第二题)
        while left and right:
            if left.val < right.val:
                h.next, left = left, left.next
            else:
                h.next, right = right, right.next
            h = h.next
        h.next = left if left else right
        return res.next   # 5.返回合并后的链表

七、桶排序经典案例

第一题：最大间距

Leetcode164. 最大间距：中等题 （详情点击链接见原题）

给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0

该题的难点在于如何用线性的时空复杂度来解决
桶排序的核心问题？每个桶的长度是多少？
我们期望将数组中的各个数等距离分配，也就是每个桶的长度相同
确定桶的数量

第二题:任务调度器

Leetcode621. 任务调度器：中等题 （详情点击链接见原题）

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态

解题思路
建立大小为 n + 1 的桶子，个数为任务数量最多的那个任务，我们可以把一个桶子看作一轮任务

1. 先从最简单的情况看，就算没有其他任务，我们完成任务 A 所需的时间应该是 (6 - 1) * 3 + 1，因为最后一个桶子，不存在等待时间
   

2. C 其实并没有对总体时间产生影响，因为它被安排在其他任务的冷却期间，而 B 和 A 数量相同，这导致在最后一个桶子中我们需要多执行一次 B 任务，现在需要的时间是 (6 - 1) * 3 + 2 = 17

总排队时间 = (桶个数 - 1) * (n + 1) + 最后一桶的任务数

3. 当冷却时间短，任务种类很多时

两个图对比可知我们刚排满了任务，此时所需的时间是 17，如果还要执行两次任务 F，此时我们执行任务所需的时间就是任务的数量

记录最大任务数量 N，看下任务数量并列最多的任务有多少个，即最后一个桶子的任务数，计算 time1 = nums1 = (N - 1) * (n + 1) + x ，time2 = len(tasks) 这是不存在空闲时间的情况（当任务种类较多时，冷却时间不够用来处理其他任务，冷却时间已被填满）

python代码解法:

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        arr = [0] * 26  # 保存任务和任务数量的哈希表
        max_tasks = 0   # 记录最多的任务数量
        count = 0  # 最多任务数量的个数
        for task in tasks:
            arr[ord(task) - ord('A')] += 1

        for i in range(26):
            if arr[i] > max_tasks:
                max_tasks = arr[i]
                count = 1
            elif max_tasks == arr[i]:
                count += 1
        return max(len(tasks), (max_tasks - 1) * (n + 1) + count)

八、区间问题

第一题：手机App防沉迷系统

面试题.手机App防沉迷系统：中等题 （详情点击链接见原题）

智能手机方便了我们生活的同时，也侵占了我们不少的时间。
“手机App防沉迷系统”能够让我们每天合理地规划手机App使用时间，在正确的时间做正确的事

解题思路
提前将输入的 APP 按照优先级降序【此时我们会先注册优先级高的 APP，后注册的 APP只要和前面注册的 APP 发生冲突，必然无法注册】

如果不存在低优先级的 APP 和高优先级的 APP 有冲突，则高优先级的 APP 提前注册对结果无影响
如果存在 低优先级的 APP 和 高优先级的 APP 有冲突，则无论低优先级的先注册还是后注册，结果都是低优先级的 APP 无法注册

python代码解法:

"""
App1 1 09:00 10:00
App2 2 09:10 09:30
"""


def convert(time):
    # 时间格式 HH:MM，小时和分钟都是两位，不足两位前面补0
    hours, minutes = map(int, time.split(":"))
    return hours * 60 + minutes


def hasInterSection(a, b):
    if b[2] <= a[2] < b[3] or a[2] <= b[2] < a[3]:
        return True
    return False


class Solution:
    def getResult(self, app_list):
        app_list.sort(key=lambda x: -x[1])
        registers = []
        for app in app_list:
            conflict = False
            for register in registers:
                if hasInterSection(app, register):
                    conflict = True
                    break
            if conflict:
                continue

            registers.append(app)

        ans = "NA"

        # 注册成功的App时段之间互不冲突，因此queryTime只会对应一个App
        for registered in registers:
            if registered[2] <= queryTime < registered[3]:
                ans = registered[0]
                break

        return ans


if __name__ == '__main__':
    s = Solution()
    # 输入获取
    app_num = int(input())  # 注册的APP数量

    # 需要注册的App:(APP名称,优先级,起始时间,结束时间)
    apps = []
    for _ in range(app_num):
        name, priority, start, end = input().split(" ")
        apps.append((name, int(priority), convert(start), convert(end)))

    # 需要查询的时间点
    queryTime = convert(input())  # 需要查询的时间结点
    print(s.getResult(apps))

九、总结

本文给大家介绍了面试中常考的关于排序问题的算法题，本文重点介绍了计数排序、快速排序、堆排序（重点）、插入排序、归并排序（重点）、桶排序、还有自定义排序规则，最后祝大家面试顺利，拿到心仪的offer~