Skip to content

Latest commit

 

History

History
482 lines (345 loc) · 12.2 KB

排序总结.md

File metadata and controls

482 lines (345 loc) · 12.2 KB

排序算法总结

低级

  1. 低级-冒泡：两两互换大的在后，小的在前，每一趟都把最大值换到最后面

O(n^2)的复杂度

defbubble_sort(nums): n=len(nums) foriinrange(n, 0, -1): forjinrange(i-1): ifnums[j] >nums[j+1]: nums[j], nums[j+1] =nums[j+1],nums[j] returnnums
  1. 低级-插入排序:
  • 从1开始，每个iter遍历第i个元素在前i-1个已经排好序的元素中的插入位置
  • i是待插入的元素位置，从i-1开始从后向前搜索
definsert_sort(nums): l=len(nums) ifl==1: returnnumsforiinrange(1, l): j=itarget=nums[i] whilej>0andtarget<nums[j-1]: nums[j] =nums[j-1] j-=1nums[j] =targetreturnnums
  1. 低级-选择排序：和冒泡相比也是每个iter选出最大或者最小的元素，但是只记录index并不每一步都进行交换，用一个额外的空间，节省中间交换的成本
defselect_sort(nums): l=len(nums) ifl==1: returnnumsforiinrange(l-1): minIndex=iforjinrange(i+1,l): ifnums[j]<nums[minIndex]: minIndex=jifminIndex!=i: nums[i], nums[minIndex] =nums[minIndex],nums[i] returnnums

高级

  1. 高级-快速排序：
  • 找benchmark，一般是left，然后从两端向内收缩，保证bench mark左边比它小，右边比它大，这样benchmark的位置就固定了，再递归去排序左边的和右边的部分
  • 和冒泡排序的差异，是冒泡每一个iter确认的是最大值，会快速排序确认的是一个中间值，所以能起到类似二分的效果
defquick_sort(nums): defpartition(nums, left, right): key=leftwhileleft<right: whileleft<rightandnums[right]>=nums[key]: right-=1whileleft<rightandnums[left]<=nums[key]: left+=1nums[left],nums[right] =nums[right],nums[left] nums[left], nums[key] =nums[key],nums[left] # 保证返回left左侧的都比右侧的小，这样可以分别排序returnleftdefsort(nums,left,right): ifleft>=right: returnmid=partition(nums, left, right) sort(nums, left, mid-1) sort(nums, mid+1, right) returnsort(nums, 0, len(nums)-1)
  1. 归并排序：自下而上的归并排序，复杂度是O(nlogn)，缺点是需要额外的空间来存储merge时有序的数组
defmerge_sort(nums): defmerge(nums, left, mid, right): i=left#左边起始j=mid+1#右边起始temp= [] #存储排序数组whilei<=midandj<=right: ifnums[i] <=nums[j]: temp.append(nums[i]) i+=1else: temp.append(nums[j]) j+=1ifi<=mid: forkinrange(i, mid+1): temp.append(nums[k]) ifj<=right: forkinrange(j, right+1): temp.append(nums[k]) foriinrange(left, right+1): nums[i] =temp[i-left] defsort(nums, left, right): ifleft>=right: returnmid= (left+right)//2sort(nums, left, mid) sort(nums, mid+1,right) merge(nums, left, mid, right) n=len(nums) ifn<=1: returnnumssort(nums, 0, len(nums) -1) returnnums

题目

  • 220存在重复元素III

  • 215 数组中的第K个最大元素

  • 703 数据流中的第K大元素

  • 40剑指offer. 最小的k个数

215. 数组中的第K个最大元素.md

给定整数数组 nums 和整数 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

提示：

1 <= k <= nums.length <= 104 -104 <= nums[i] <= 104
  1. 堆排序
classSolution: deffindKthLargest(self, nums: List[int], k: int) ->int: heap= [xforxinnums[:k]] heapq.heapify(heap) n=len(nums) foriinrange(k, n): ifnums[i]>heap[0]: heapq.heappop(heap) heapq.heappush(heap,nums[i]) returnheap[0]
  • python heapq是完全二叉树的实现，parent<=child
  • Heappop->下降：当root节点被heappop，会把叶子节点放到root，依次和child中更小的节点进行交换，直到再次成为叶节点
def_siftup(heap, pos): endpos=len(heap) startpos=posnewitem=heap[pos] # Bubble up the smaller child until hitting a leaf.childpos=2*pos+1# 左节点，默认替换左节点whilechildpos<endpos: # Set childpos to index of smaller child.rightpos=childpos+1# 右节点ifrightpos<endposandnotheap[childpos] <heap[rightpos]: childpos=rightpos# 当右节点比较小时，应交换的是右节点# Move the smaller child up.heap[pos] =heap[childpos] pos=childposchildpos=2*pos+1# The leaf at pos is empty now. Put newitem there, and bubble it up# to its final resting place (by sifting its parents down).heap[pos] =newitem_siftdown(heap, startpos, pos)
  • Heappush上浮：把push的元素放在叶节点，如果比parent小就和parent进行替换，
def _siftdown(heap, startpos, pos): newitem = heap[pos] # Follow the path to the root, moving parents down until finding a place # newitem fits. while pos > startpos: parentpos = (pos - 1) >> 1 parent = heap[parentpos] if newitem < parent: heap[pos] = parent pos = parentpos continue break heap[pos] = newitem
  • heapify
def heapify(x): """Transform list into a heap, in-place, in O(len(x)) time.""" n = len(x) for i in reversed(range(n//2)): _siftup(x, i)
  1. 快速排序通用解法
    • 不需要对整体数组进行排序，只需要找到第k个数即可
classSolution: deffindKthLargest(self, nums: List[int], k: int) ->int: defpartition(nums, left, right): key=leftwhileleft<right: whileleft<rightandnums[right]>=nums[key]: right-=1whileleft<rightandnums[left]<=nums[key]: left+=1nums[left], nums[right] =nums[right],nums[left] nums[left],nums[key] =nums[key],nums[left] returnleftdeftopk(nums, k, left, right): ifleft>=right: returnmid=partition(nums,left,right) ifmid==k: returnelifmid<k: topk(nums,k, mid+1, right) else: topk(nums,k,left, mid-1) l=len(nums) topk(nums, l-k, 0, l-1) print(nums) returnnums[l-k]

220. 存在重复元素 III.md

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。

如果存在则返回 true，不存在返回 false。

示例 1：

输入：nums = [1,2,3,1], k = 3, t = 0 输出：true

示例 2：

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

示例 3：

输入：nums = [1,5,9,1,5,9], k = 2, t = 3 输出：false

提示：

0 <= nums.length <= 2 * 104 -231 <= nums[i] <= 231 - 1 0 <= k <= 104 0 <= t <= 231 - 1 
classSolution: defcontainsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) ->bool: bucket=dict() ift<0: returnFalseforiinrange(len(nums)): nth=nums[i] // (t+1) ifnthinbucket: returnTrueifnth-1inbucketandabs(nums[i] -bucket[nth-1]) <=t: returnTrueifnth+1inbucketandabs(nums[i] -bucket[nth+1]) <=t: returnTruebucket[nth] =nums[i] ifi>=k: bucket.pop(nums[i-k] // (t+1)) returnFalse

40剑指offer. 最小的k个数.md

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

输入：arr = [3,2,1], k = 2 输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1 输出：[0]

限制：

0 <= k <= arr.length <= 10000 0 <= arr[i] <= 10000
  1. 堆排序
classSolution: defgetLeastNumbers(self, arr: List[int], k: int) ->List[int]: ifk==0: returnlist() nums= [-iforiinarr[:k]] heapq.heapify(nums) foriinarr[k:]: if-i>nums[0]: heapq.heappop(nums) heapq.heappush(nums, -i) return [-xforxinnums]
  1. 快速排序
classSolution: defgetLeastNumbers(self, arr: List[int], k: int) ->List[int]: defpartition(nums, left, right): key=leftwhileleft<right: whileleft<rightandnums[right]>=nums[key]: right-=1whileleft<rightandnums[left]<=nums[key]: left+=1nums[left], nums[right] =nums[right],nums[left] nums[left],nums[key] =nums[key],nums[left] returnleftdefquick_sort(nums, left, right): ifleft>=right: returnmid=partition(nums, left, right) ifk<mid: quick_sort(nums, left, mid-1) else: quick_sort(arr, mid+1, right) l=len(arr) ifk>l: returnarrquick_sort(arr, 0, l-1) returnarr[:k]

快速排序解法

  1. 注意partition过程中，保证右边是>=key， 左边是<=key，且左右是不对称的需要先遍历右边
  2. 在sort过程中，可以通过和k判断位置只对一半的位置进行排序
  3. 注意sort过程的停止条件，默认是left>=right，如果找k大的停止条件还有mid==k

703. 数据流中的第 K 大元素.md

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

请实现 KthLargest 类：

KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。 int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

示例：

输入： ["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] 输出： [null, 4, 5, 5, 8, 8]

解释： KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4 kthLargest.add(5); // return 5 kthLargest.add(10); // return 5 kthLargest.add(9); // return 8 kthLargest.add(4); // return 8

提示：

1 <= k <= 104 0 <= nums.length <= 104 -104 <= nums[i] <= 104 -104 <= val <= 104 最多调用 add 方法 104 次 题目数据保证，在查找第 k 大元素时，数组中至少有 k 个元素 
classKthLargest: def__init__(self, k: int, nums: List[int]): self.k=kself.que=numsheapq.heapify(self.que)# heapify是原地把list变成小根堆defadd(self, val: int) ->int: heapq.heappush(self.que, val) whilelen(self.que)>self.k: heapq.heappop(self.que) returnself.que[0]

Tips

优先队列算法（最小堆）

  1. heapq是二叉树结构，特点是root<=children。所以有heap[k]<=heap[2K+1] & heap[k] <=heap[2K+2]的特点，且最小元素是root
  2. heapq单次插入时间复杂度是log(k)，相比使用list每次add之后sort的时间复杂度是O(klog(k))
  3. 永远只维护K个最大的元素，这样最小堆的root就是第K大元素
  4. pop弹出最小元素，heap[0]最小元素
close