例1：LeetCode 第 75 题：颜色分类
传送门：75. 颜色分类。
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。示例:
输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2]进阶：
- 一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。- 你能想出一个仅使用常数空间的一趟扫描算法吗？
说明：三路快排的 partition 是非常基础且重要的算法，一定要掌握。
Python 代码1：分别统计个数，然后逐个赋值，感觉有些麻烦，但是思路还是很清晰的
class Solution:
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
counter = [0] * 3
for num in nums:
counter[num] += 1
i = 0
for _ in range(counter[0]):
nums[i] = 0
i += 1
for _ in range(counter[1]):
nums[i] = 1
i += 1
for _ in range(counter[2]):
nums[i] = 2
i += 1
Python 代码2：与上一个版本等价
class Solution:
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
counter = [0] * 3
for num in nums:
counter[num] += 1
i = 0
for idx, count in enumerate(counter):
for _ in range(count):
nums[i] = idx
i += 1
Python 代码3：三路快排，不用借助额外的存储空间，直接遍历一遍数组，通过交换元素的位置就完成了排序
class Solution:
def sortColors(self, nums):
l = len(nums)
# 循环不变量的定义：
# [0, zero] 中的元素全部等于 0
# (zero, i) 中的元素全部等于 1
# [two, l - 1] 中的元素全部等于 2
zero = -1
two = l
i = 0 # 马上要看的位置
while i < two:
if nums[i] == 0:
zero += 1
nums[zero], nums[i] = nums[i], nums[zero]
i += 1
elif nums[i] == 1:
i += 1
else:
two -= 1
nums[two], nums[i] = nums[i], nums[two]
练习 1：LeetCode 第 88 题：从后向前归并两个有序数组
传送门：英文网址：88. Merge Sorted Array ，中文网址：88. 合并两个有序数组 。
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
- 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
- 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:
输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 输出: [1,2,2,3,5,6]
分析：其实就是归并排序，不过从后向前归并是这道题的考点。注意分 4 种情况，代码的写法其实是相对固定的。
思路1：可以使用标准的归并排序来做。
Python 代码：从前向后写
class Solution:
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
nums3 = nums1.copy()
i = 0
j = 0
for k in range(m + n):
if i == m: # i 用完了
nums1[k] = nums2[j]
j += 1
elif j == n:
nums1[k] = nums3[i]
i += 1
elif nums3[i] < nums2[j]:
nums1[k] = nums3[i]
i += 1
else:
nums1[k] = nums2[j]
j += 1
思路2：考虑到这道题的特殊性，即 nums1 有足够的空间，因此，我们可以从后向前归并，每次从两个数组的末尾选出最大的元素放在 nums1 的末尾，而不使用额外的数组空间。
你可能会担心，nums1 之前有效的元素会不会被覆盖掉，但在这题中，这种情况是不可能出现的。在实现的时候，还是要特别注意一些边界条件。
Python 代码：从后向前写
class Solution:
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
i = m - 1
j = n - 1
for k in range(m + n - 1, -1, -1):
if i == -1:
nums1[k] = nums2[j]
j -= 1
elif j == -1:
nums1[k] = nums1[i]
i -= 1
elif nums1[i] > nums2[j]:
nums1[k] = nums1[i]
i -= 1
else:
nums1[k] = nums2[j]
j -= 1
练习 2：LeetCode 第 215 题：数组第 k 大的元素
传送门：英文网址：215. Kth Largest Element in an Array ，中文网址：215. 数组中的第K个最大元素 。
在未排序的数组中找到第 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：排序，然后返回倒数第 个元素，索引是
；
思路2：partition ，逐渐减少搜索的范围，partition 的核心是大于等于的放过，小于的才做操作，因为要让小于的挪到前面去，还能保证元素的相对位置不变； ，注意一些边边角角的细节，+1 和 -1 要特别小心。
Python 代码：partition 的过程一定要在理解的基础上，熟记
# 215. 数组中的第 K 个最大元素
# 在未排序的数组中找到第 k 个最大的元素。
# 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
class Solution:
# 数组中的第 K 个最大元素
# 数组中第 k 大的元素，它的索引是 len(nums) - k
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
size = len(nums)
if size < k:
raise Exception('程序出错')
# [0,1,2,3,4,5]
# 第 k 大元素的索引是 len(nums) - k
left = 0
right = len(nums) - 1
while True:
index = self.__partition(nums, left, right)
if index == len(nums) - k:
return nums[index]
if index > len(nums) - k:
right = index - 1
else:
left = index + 1
def __partition(self, nums, left, right):
"""
partition 是必须要会的子步骤，一定要非常熟练
在 [left, right] 这个区间执行 partition
遇到比第一个元素大的或等于的，就放过，遇到小的，就交换
:param nums:
:param left:
:param right:
:return:
"""
pivot = nums[left]
k = left
for index in range(left + 1, right + 1):
if nums[index] < pivot:
k += 1
nums[k], nums[index] = nums[index], nums[k]
nums[left], nums[k] = nums[k], nums[left]
return k
if __name__ == '__main__':
nums = [3, 7, 8, 1, 2, 4]
solution = Solution()
result = solution.findKthLargest(nums, 2)
print(result)
思路3：使用堆。
Python 代码1：使用容量为 k 的小顶堆，元素个数小于 k 的时候，放进去就是了；元素个数大于 k 的时候，小于堆顶元素，就扔掉，大于堆顶元素，就替换。
import heapq
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
size = len(nums)
if k > size:
raise Exception('程序出错')
# 堆有序数组
h = []
for num in nums:
if len(h) < k:
heapq.heappush(h, num)
else:
if num < h[0]:
pass
else:
heapq.heappushpop(h, num)
return h[0]
Python 代码2：与 Python 代码1 等价的写法
import heapq
# 还可以参考：https://leetcode.com/problems/kth-largest-element-in-an-array/discuss/167837/Python-or-tm
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
L = []
for index in range(k):
# 默认是最小堆
heapq.heappush(L, nums[index])
for index in range(k, len(nums)):
top = L[0]
if nums[index] > top:
# 看一看堆顶的元素，只要比堆顶元素大，就替换堆顶元素
heapq.heapreplace(L, nums[index])
# 最后堆顶中的元素就是堆中最小的，整个数组中的第 k 大元素
return L[0]
Python 代码3：使用大顶堆，全部放进去以后，再往外 pop
import heapq
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
l = [(-num, num) for num in nums]
heapq.heapify(l)
for _ in range(k - 1):
heapq.heappop(l)
return l[0][1]
说明：Python 中的 heapq 可以传入 tuple，heapq 会根据 tuple 的 0 号索引元素进行堆的操作。
Python 代码4：与 Python 代码 3 等价的写法
import heapq
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
l = [(-num, num) for num in nums]
heapq.heapify(l)
for _ in range(k):
_, res = heapq.heappop(l)
return res
（本节完）
网友评论