排序

912. Sort an Array

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def partition(arr, low, high):            # 将pivot放置于最终排序位置，并返回index
            idx_pivot = random.randint(low, high) # [low, high]
            arr[low], arr[idx_pivot] = arr[idx_pivot], arr[low]
            pivot = arr[low]
            left, right = low, high
            while left < right:
                while left < right and arr[right] >= pivot:
                    right -= 1
                arr[left] = arr[right]
                while left < right and arr[left] <= pivot:
                    left += 1
                arr[right] = arr[left]
            arr[left] = pivot
            return left
        def quick_sort(arr, low, high):
            if low >= high:
                return
            mid = partition(arr, low, high)
            quick_sort(arr, low, mid - 1)
            quick_sort(arr, mid + 1, high)
        quick_sort(nums, 0, len(nums) - 1)
        return nums

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def merge_sort(arr, low, high):
            if low >= high:
                return 
            mid = low + high >> 1
            merge_sort(arr, low, mid)             # [low, mid]
            merge_sort(arr, mid + 1, high)        # [mid+1, high]
            tmp = []                              # 暂存[low, high]排序结果
            left, right = low, mid + 1
            while left <= mid and right <= high:
                if arr[left] < arr[right]:
                    tmp.append(arr[left])
                    left += 1
                else:
                    tmp.append(arr[right])
                    right += 1
            tmp += arr[left:mid+1]                # 还剩余一部分（已经有序）
            tmp += arr[right:high+1]
            arr[low:high+1] = tmp                 # 暂存的有序部分覆盖掉原数组
        merge_sort(nums, 0, len(nums) - 1)
        return nums

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        nums = [0] + nums                             # 1-index：左孩子 2*i
                                                      #          右孩子 2*i + 1
        def max_heapify(arr, i, end):
            j = 2 * i                                 # 左孩子
            while j <= end:
                if j+1 <= end and arr[j+1] > arr[j]:  # 选择左、右孩子中较大的一个
                    j += 1
                if arr[i] < arr[j]:
                    arr[i], arr[j] = arr[j], arr[i]
                    i = j                             # 往下继续调整
                    j = 2 * i
                else:
                    break
        for i in range(n//2, 0, -1):                  # 从首个非叶子节点开始调整(n//2)
            max_heapify(nums, i, n)
        for j in range(n, 0, -1):                     # 堆排序
            nums[1], nums[j] = nums[j], nums[1]       # 堆顶与堆底元素互换
            max_heapify(nums, 1, j-1)                 # 重新调整堆
        return nums[1:]                               # 删除首个占位元素

215. Kth Largest Element in an Array

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        max_heap = [-num for num in nums]
        heapq.heapify(max_heap)
        for _ in range(k - 1):
            heapq.heappop(max_heap)
        return -max_heap[0]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        min_heap = []
        for num in nums:
            heapq.heappush(min_heap, num)
            if len(min_heap) > k:
                heapq.heappop(min_heap)
        return min_heap[0]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def partition(arr, low, high):
            idx_pivot = random.randint(low, high)
            arr[low], arr[idx_pivot] = arr[idx_pivot], arr[low]
            pivot = arr[low]
            left, right = low, high
            while left < right:
                while left < right and arr[right] >= pivot:
                    right -= 1
                arr[left] = arr[right]
                while left < right and arr[left] <= pivot:
                    left += 1
                arr[right] = arr[left]
            arr[left] = pivot
            return left
        def quick_sort(arr, low, high):
            if low >= high:
                return
            mid = partition(arr, low, high)
            if mid < (idx_k := len(arr)-k):
                quick_sort(arr, mid+1, high)
            elif mid > idx_k:
                quick_sort(arr, low, mid-1)
            else:
                return
        quick_sort(nums, 0, len(nums)-1)
        return nums[-k]

• 时间复杂度：，即为快速排序划分枢轴的最差复杂度。即每次都划分为和的区间。
• 空间复杂度：

剑指 Offer 40. 最小的k个数

148. Sort List

class Solution:
    def merge_two_lists(self, list1, list2):
        dummy = ListNode(-1)
        p = dummy
        while list1 and list2:
            if list1.val < list2.val:
                p.next = list1
                list1 = list1.next
            else:
                p.next = list2
                list2 = list2.next
            p = p.next
        p.next = list1 if list1 else list2
        return dummy.next
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        mid = slow.next
        slow.next = None                     # cut，断链
        l1 = self.sortList(head)
        l2 = self.sortList(mid)
        return self.merge_two_lists(l1, l2)  # merge，合并

• 时间复杂度：
• 空间复杂度：

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return
        length_list = 0             # 链表长度
        p = head
        while p:
            p = p.next
            length_list += 1
        dummy = ListNode(-1, head)
        base = 1                    # 每次归并的子链表长度
        while base < length_list:
            pre, h = dummy, dummy.next
            while h:
                h1, i = h, base     # 归并链表 1
                while h and i:
                    h = h.next
                    i -= 1
                if i:               # 剩余长度不足base（已经有序）
                    break
                h2, i = h, base     # 归并链表 2
                while h and i:
                    h = h.next
                    i -= 1
                len1, len2 = base, base - i
                while len1 and len2:           # 迭代合并
                    if h1.val < h2.val:
                        pre.next = h1
                        h1 = h1.next
                        len1 -= 1
                    else:
                        pre.next = h2
                        h2 = h2.next
                        len2 -= 1
                    pre = pre.next
                pre.next = h1 if len1 else h2
                while len1 > 0 or len2 > 0:    # 将pre指针移动到归并链表尾部（必须指定>0）
                    pre = pre.next
                    len1, len2 = len1 - 1, len2 - 1
                pre.next = h
            base *= 2
        return dummy.next

• 时间复杂度：
• 空间复杂度：

剑指 Offer 51. 数组中的逆序对

class Solution:
    def reversePairs(self, nums: List[int]) -> int:

        def merge_sort(arr, low, high):
            if low >= high:
                return 0

            mid = low + high >> 1
            inversed_pairs = merge_sort(arr, low, mid) + merge_sort(arr, mid + 1, high)

            tmp = []
            left, right = low, mid + 1

            while left <= mid and right <= high:
                if arr[left] <= arr[right]:           # 元素相同，必须先添加左半部分 
                    tmp.append(arr[left])
                    left += 1
                else:                                 # 右半部分较小时，添加逆序对数
                    tmp.append(arr[right])
                    right += 1
                    inversed_pairs += mid - left + 1

            tmp += arr[left:mid+1]                    # 剩余一部分无须计算逆序对
            tmp += arr[right:high+1]

            arr[low:high+1] = tmp
            return inversed_pairs

        return merge_sort(nums, 0, len(nums) - 1)

• 时间复杂度：
• 空间复杂度：，临时数组空间

347. Top K Frequent Elements

179. Largest Number

对于中的任意两个值和，我们无法直接从常规角度上确定其大小/先后关系。
但我们可以根据「结果」来决定和的排序关系：
如果拼接结果 要比好，那么我们会认为应该放在前面。
另外，注意我们需要处理前导零（最多保留一位）。

from functools import cmp_to_key

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        strs = list(map(str, nums))

        # 自定义排序规则
        def cmp(a: str, b: str):
            if a + b == b + a:
                return 0
            elif a + b > b + a:
                return 1
            else:
                return -1

        strs.sort(key=cmp_to_key(cmp), reverse=True)
        # 注意前导0的特判
        return ''.join(strs) if strs[0] != '0' else '0'