算法长征（15）排序*

发表于 更新于 分类于 ， 阅读次数： 本文字数： 11k 阅读时长 ≈ 20 分钟

排序

一、快速排序

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

（最小）堆排序算法：https://docs.python.org/zh-cn/3/library/heapq.html

  • ==快速选择、堆排序==
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        # 堆排序
        if k == 0:
            return list()
        hp = [ -x for x in arr[:k]]
        heapq.heapify(hp)
        for i in range(k, len(arr)):
            if -hp[0] > arr[i]:
                heapq.heappop(hp)
                heapq.heappush(hp, -arr[i])
        arr = [-x for x in hp]
        return arr   
        
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        # 快速选择
        if k == 0:
            return []
        def quickSelect(low, high, k):
            pvoit = random.randint(low, high)
            arr[pvoit], arr[low] = arr[low], arr[pvoit]
            base = arr[low] 
            i = low
            for j in range(low+1, high+1):
                if arr[j] < base:
                    arr[i+1], arr[j] = arr[j], arr[i+1]
                    i += 1
            arr[low], arr[i] = arr[i], arr[low] 
            if i == k - 1:
                return arr[:k]
            elif i < k - 1:
                return quickSelect(i+1, high, k)
            else: 
                return quickSelect(low, i-1, k)

        return quickSelect(0, len(arr) - 1, k)

https://leetcode.cn/problems/kth-largest-element-in-an-array/solution/cpython3java-1da-gen-dui-diao-ku-2shou-l-xveq/

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

  • 小根堆调库、快速选择
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for num in nums:
            if len(heap) >= k:
                if num > heap[0]: # 注意替换条件
                    heapq.heapreplace(heap, num)
            else:
                heapq.heappush(heap, num)
        return heap[0]
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # 快速选择
        def findTopk(low, high):
            pvoit = random.randint(low, high)
            nums[pvoit], nums[low] = nums[low], nums[pvoit]
            base = nums[low]
            i = low 
            for j in range(low + 1, high + 1):
                if nums[j] > base:
                    nums[i + 1], nums[j] = nums[j], nums[i + 1]
                    i += 1
            nums[i], nums[low] = nums[low], nums[i]
            if i == k - 1:
                return nums[i]
            elif i < k - 1:
                return findTopk(i + 1, high)
            else:
                return findTopk(low, i - 1)
        return findTopk(0, len(nums) - 1)

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

  • 【基于快排】+【拼接字符串】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def minNumber(self, nums: List[int]) -> str:
        n = len(nums)
        def _smallA(a, b):
            return True if a + b < b + a else False
        def partition(l, r):
            pivot = random.randint(l, r)
            nums[pivot], nums[l] = nums[l], nums[pivot]
            base = nums[l]
            i = l
            for j in range(l+1, r+1): # r+1 遍历到r
                if _smallA(nums[j], base):
                    nums[j], nums[i+1] = nums[i+1], nums[j] # i + 1 与i前面的换
                    i += 1
            nums[l], nums[i] = nums[i], nums[l]
            return i
        def quick_sort(l, r):
            if r - l <= 0:
                return
            mid = partition(l, r)
            quick_sort(l, mid - 1)
            quick_sort(mid + 1, r)
        nums = [str(num) for num in nums]
        quick_sort(0, len(nums) - 1)
        return "".join(nums).lstrip()
  • 内置函数：cmp_to_key，单个元素并没有一个绝对的大小的情况
1
2
3
4
5
class Solution:    
  def largestNumber(self, nums: List[int]) -> str:
        nums.sort(key=cmp_to_key(lambda x,y: int(str(y)+str(x)) - int(str(x)+str(y))))
        ans = ''.join([str(num) for num in nums])
        return str(int(ans))

从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

  • 集合 Set + 遍历，排序 + 遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def isStraight(self, nums: List[int]) -> bool:
        pset = set()
        mi, ma = 14, -1
        for num in nums:
            if num == 0:
                continue
            if num in pset:
                return False
            mi = min(mi, num)
            ma = max(ma, num)
            pset.add(num)
        return ma - mi < 5
    def isStraight(self, nums: List[int]) -> bool:
        joker = 0
        nums.sort() # 数组排序
        for i in range(4):
            if nums[i] == 0: joker += 1 # 统计大小王数量
            elif nums[i] == nums[i + 1]: return False # 若有重复，提前返回 false
        return nums[4] - nums[joker] < 5 # 最大牌 - 最小牌 < 5 则可构成顺子

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

  • 大小堆排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
heappush(self.B, -heappushpop(self.A, num))class MedianFinder:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.minheap = []
        self.maxheap = []

    def addNum(self, num: int) -> None:
        if len(self.minheap) != len(self.maxheap):
          	# heappush(self.B, -heappushpop(self.A, num))
            heappush(self.minheap, num)
            heappush(self.maxheap, -heappop(self.minheap))
        else: # 【len等于时，min多】
            heappush(self.maxheap, -num)
            heappush(self.minheap, -heappop(self.maxheap))

    def findMedian(self) -> float:
        return self.minheap[0] if len(self.minheap) != len(self.maxheap) else (self.minheap[0] - self.maxheap[0] ) / 2.0

二、归并排序

「归并排序」是分治思想的典型应用。

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

那么求逆序对和归并排序又有什么关系呢？

两个已排序的序列等待合并，记录计算逆序对的数量；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def mergeSort(nums, low, high):
            if low >= high:     # 递归终止
                return 0        
            ans = 0             # 记录当前逆序对数目
            '''递归排序'''
            mid = low+(high-low)//2     
            ans += mergeSort(nums, low, mid)        # 左半部分逆序对数目
            ans += mergeSort(nums, mid+1, high)     # 右半部分逆序对数目

            '''nums[low, mid] 和 nums[mid+1, high] 已排序好'''
            tmp = []        # 记录nums[low, high]排序结果
            left, right = low, mid+1
            while left<=mid and right<=high:
                if nums[left] <= nums[right]:
                    tmp.append(nums[left])
                    left += 1
                else:       # 后半部分值较小，出现了逆序
                    tmp.append(nums[right])
                    right += 1
                    ans += mid+1-left       # 当前值 nums[right] 贡献的逆序对个数为 mid+1-left
                    '''解释：若nums[left] > nums[right]，
                       则nums[left, mid] > nums[right]均成立，共 mid+1-left 项'''
            
            '''左或右数组需遍历完（最多只有一个未遍历完）'''
            while left<=mid:
                tmp.append(nums[left])
                left += 1

            while right<=high:
                tmp.append(nums[right])
                right += 1
                # ans += mid+1-left     # 此时，前半部分一定已经遍历完了，即left=mid+1，因此无需再更新结果
            nums[low:high+1] = tmp
            return ans
        '''主程序'''
        return mergeSort(nums, 0, len(nums)-1)

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

img

输入：head = [4,2,1,3] 输出：[1,2,3,4]

  • 归并排序 + 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 时间空间复杂度分别为 O(nlogn) 和 O(1) 【归并排序】
        # 【切分数组】
        if not head or not head.next:
            return head
        slow, fast = head, head.next # 快慢指针【如何】初始化
        while fast and fast.next:
            fast, slow = fast.next.next, slow.next
        mid, slow.next = slow.next, None # None截断
        left, right = self.sortList(head), self.sortList(mid) # 递归
        # 【合并链表】
        h = dummy = ListNode(0) # 新建节点的合并
        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 dummy.next

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

输入：lists = [[1,4,5], [1,3,4], [2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6

  • 【优先队列】[推荐] 维护多个链表对象；时间：O(nlog(k))，n 是所有链表中元素总和，k 是链表个数；
  • 【归并排序】链表两两合并，递归占用很多空间；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        # 优先队列 维护多个链表对象
        h = dummy = ListNode(0)
        heap = []
        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(heap, (lists[i].val, i))
                lists[i] = lists[i].next
        while heap:
            val, idx = heapq.heappop(heap)
            h.next = ListNode(val)
            h = h.next
            if lists[idx]:
                heapq.heappush(heap, (lists[idx].val, idx))
                lists[idx] = lists[idx].next
        return dummy.next
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
      	# 【归并排序】链表两两合并
        if not lists:return 
        n = len(lists)
        return self.merge(lists, 0, n-1)
    def merge(self,lists, left, right):
        if left == right:
            return lists[left]
        mid = left + (right - left) // 2
        l1 = self.merge(lists, left, mid)
        l2 = self.merge(lists, mid+1, right)
        return self.mergeTwoLists(l1, l2)
    def mergeTwoLists(self,l1, l2):
        if not l1:return l2
        if not l2:return l1
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

三、堆排序

Python 十大排序算法：https://leetcode.cn/problems/sort-an-array/solution/python-shi-xian-de-shi-da-jing-dian-pai-xu-suan-fa/

堆排序是利用堆这个数据结构设计的排序算法。

算法描述：

  • 建堆，从底向上==调整堆==，使得父亲节点比孩子节点值大，构成大顶堆；
  • 交换堆顶和最后一个元素，重新调整堆。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 递归写法
    def adjust_heap(nums, startpos, endpos):
        pos = startpos
        chilidpos = pos * 2 + 1
        if chilidpos < endpos:
            rightpos = chilidpos + 1
            if rightpos < endpos and nums[rightpos] > nums[chilidpos]:
                chilidpos = rightpos
            if nums[chilidpos] > nums[pos]:
                nums[pos], nums[chilidpos] = nums[chilidpos], nums[pos]
                adjust_heap(nums, pos, endpos)
    # 迭代写法
    def adjust_heap(nums, startpos, endpos):
        newitem = nums[startpos]
        pos = startpos
        childpos = pos * 2 + 1
        while childpos < endpos:
            rightpos = childpos + 1
            if rightpos < endpos and nums[rightpos] >= nums[childpos]:
                childpos = rightpos
            if newitem < nums[childpos]:
                nums[pos] = nums[childpos]
                pos = childpos
                childpos = pos * 2 + 1
            else:
                break
        nums[pos] = newitem

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

请实现 KthLargest 类：

  • KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
  • int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.heap = []
        self.size = k 
        for num in nums:
            self._push(num)
    def _push(self, num):
        if self.size <= len(self.heap):
            if self.heap[0] < num:
                heapq.heappop(self.heap)
                heapq.heappush(self.heap, num)
        else:
            heapq.heappush(self.heap, num)

    def add(self, val: int) -> int:
        self._push(val)
        return self.heap[0]

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

  • API : return [c[0] for c in Counter(nums).most_common(k)]
  • 快速选择
  • 堆排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        def findTopk(low, high):
            pivot = random.randint(low, high)
            nums_cnt[pivot], nums_cnt[low] = nums_cnt[low], nums_cnt[pivot]
            base = nums_cnt[low][1]
            i = low
            for j in range(low + 1, high + 1):
                if nums_cnt[j][1] > base:
                    nums_cnt[i + 1], nums_cnt[j] = nums_cnt[j], nums_cnt[i + 1]
                    i += 1
            nums_cnt[i], nums_cnt[low] = nums_cnt[low], nums_cnt[i]
            if i == k - 1:
                return nums_cnt[:k]
            elif i < k - 1:
                return findTopk(i + 1, high)
            else:
                return findTopk(low, i - 1)
        
        nums_cnt = list(Counter(nums).items())
        res = findTopk(0, len(nums_cnt) - 1)
        return [r[0] for r in res]
		def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # 堆排序
        # heapq.nlargest(n, iterable, key=None)
        # 【val, key】 heapq 中优先比[0]
        conter = Counter(nums)
        heap = []
        for key, val in conter.items():
            if len(heap) >= k:
                if val > heap[0][0]:
                    heapq.heapreplace(heap,(val, key))
            else:
                heapq.heappush(heap,(val, key))
        return [item[1] for item in heap]

给定两个以升序排列的整数数组 nums1 和 nums2 , 以及一个整数 k 。定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。请找到和最小的 k 个数对 (u1,v1), (u2,v2) ... (uk,vk) 。

输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3 输出: [1,2],[1,4],[1,6] 解释: 返回序列中的前 3 对数： [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

  • 多路归并【优先队列】、二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        # 【BFS】【优先队列, 排序输出交给堆】【去重】
        m, n = len(nums1), len(nums2)
        heap = [(nums1[0] + nums2[0], 0, 0)]
        res = []
        visited = set()
        while heap:
            val, i, j = heapq.heappop(heap) 
            res.append((nums1[i], nums2[j]))
            visited.add((i, j))
            if len(res) == k:
                return res
            if i + 1 < m and (i + 1, j) not in visited:
                heapq.heappush(heap, (nums1[i + 1] + nums2[j], i + 1, j))
                visited.add((i + 1, j))
            if j + 1 < n and (i, j + 1) not in visited:
                heapq.heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1))
                visited.add((i, j + 1))
        return res

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        n = len(intervals)
        intervals.sort(key = lambda x: x[0])
        ans = []
        ans.append(intervals[0])
        for i in range(1, n):
            if ans[-1][1] >= intervals[i][0]:
                if (t := intervals[i][1]) > ans[-1][1]:
                    ans[-1][1] = t
            else:
                ans.append(intervals[i])
        return ans

给定两个数组，arr1 和 arr2，

  • arr2 中的元素各不相同
  • arr2 中的每个元素都出现在 arr1 中

对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

  • 自定义排序
1
2
3
4
5
6
class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        def cmp(k):
            return (0, cmpDict[k]) if k in cmpDict else (1, k) 
        cmpDict = {val:i for i, val in enumerate(arr2)}
        return sorted(arr1, key = cmp)