常考常考高频率

1.快排（双指针）

快排，归并排序，堆排序

#快速排序O（nlogn）
def quick_sort(array, left, right):if left < right:mid = partition(array, left, right)quick_sort(array, left, mid)quick_sort(array, mid+1, right)return arraydef partition(array, left, right):pivot = array[left]while left < right:while (left <right and array[right]>= pivot):right -= 1array[left] = array[right]while (left< right and array[left] <= pivot):left += 1array[right] = array[left]array[left] = pivotreturn left

# 归并排序O（nlogn）
def merge(left, right):array = []while (len(left)>0 and len(right)>0):if left[0] < right[0]:array.append(left.pop(0))else:array.append(right.pop(0))array += leftarray += rightreturn arraydef merge_sort(array):if len(array) <= 1:  #如果array只有一个元素直接退出return arraymid = len(array)//2left = merge_sort(array[:mid])right = merge_sort(array[mid:])array_new = merge(left, right)return array_new

2. 第K大（快排or 堆）

力扣215.数组中的第K个最大的元素
912.排序数组

class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:pivot = nums[0]small,equal,big = [],[],[]for i in nums:if i> pivot:big.append(i)elif i < pivot:small.append(i)else:equal.append(i)if len(big) >= k:return self.findKthLargest(big, k)elif len(big)< k and len(big) + len(equal)>=k:return pivotelse:return self.findKthLargest(small,k-len(big)-len(equal))

找到第K大的元素

'''快速排序'''
class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:def partition(nums, left, right):pivot = nums[left]while left< right:while (left< right and nums[right]>=pivot):right -= 1nums[left] = nums[right]while (left<right and nums[left] <= pivot):left += 1nums[right] = nums[left]nums[left] = pivotreturn leftdef randomPartition(nums, left, right):   # 随机选择pivot，防止最坏情况nums是降序pivot_index = random.randint(left, right)nums[left], nums[pivot_index] = nums[pivot_index], nums[left]return partition(nums, left, right)def topKSplit(nums, left, right, k):  #找到第k小的元素，如果是第1小，则index=0mid = randomPartition(nums, left, right)if mid == k-1:return nums[mid]elif mid < k-1:return topKSplit(nums, mid+1, right, k)else:return topKSplit(nums, left, mid-1, k)n = len(nums)return topKSplit(nums, 0, n-1, n-k+1)  #第k大=第n-k+1小

堆排序？？？

'''堆排序'''
class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:def maxHeapify(arr, i, end):j = 2*i + 1while j <= end:if j+1 <= end and arr[j+1] > arr[j]:j += 1if arr[i] < arr[j]:arr[i], arr[j] = arr[j], arr[i]i = jj = 2*i + 1else:breakdef maxHepify(arr, i, end):     # 大顶堆j = 2*i + 1                 # j为i的左子节点【建堆时下标0表示堆顶】while j <= end:             # 自上而下进行调整if j+1 <= end and arr[j+1] > arr[j]:    # i的左右子节点分别为j和j+1j += 1                              # 取两者之间的较大者if arr[i] < arr[j]:             # 若i指示的元素小于其子节点中的较大者arr[i], arr[j] = arr[j], arr[i]     # 交换i和j的元素，并继续往下判断i = j                       # 往下走：i调整为其子节点jj = 2*i + 1                 # j调整为i的左子节点else:                           # 否则，结束调整breakn = len(nums)# 建堆【大顶堆】for i in range(n//2-1, -1, -1):         # 从第一个非叶子节点n//2-1开始依次往上进行建堆的调整maxHepify(nums, i, n-1)# 排序：依次将堆顶元素（当前最大值）放置到尾部，并调整堆# k-1次重建堆（堆顶元素），或 k次交换到尾部（倒数第k个元素）for j in range(n-1, n-k-1, -1):nums[0], nums[j] = nums[j], nums[0]     # 堆顶元素（当前最大值）放置到尾部jmaxHepify(nums, 0, j-1)                 # j-1变成尾部，并从堆顶0开始调整堆return nums[-k]

3.滑动窗口的最大值（双端队列deque）

4. 岛屿数量 （dfs）

5. 二叉树遍历（队列等）

6. 旋转数组（二分）

7.完全平方数、零钱兑换（动态规划）

8.反转链表