【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题：翻转对、买卖股票最佳时机、数组中第K个最大/最小元素

# 分治排序算法扩展
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def merge(left, right):
            # 统计前面比后面大的翻转对个数
            j = 0
            for i in range(len(left)):
                while j < len(right) and left[i] > 2 * right[j]:
                    j += 1
                self.count += j
            # 合并两个有序列表
            res = []
            while  len(left) > 0 and len(right) > 0:
                if left[0] < right[0]:
                    res.append(left.pop(0))
                else:
                    res.append(right.pop(0))
            if left:
                res.extend(left)
            if right:
                res.extend(right)
            return res
        def mergeSort(arr):
            n =len(arr)
            if n < 2:
                return arr
            middle = n // 2
            left = arr[:middle]
            right = arr[middle:]
            sort_left = mergeSort(left)
            sort_right = mergeSort(right)
            return merge(sort_left, sort_right)
        self.count = 0
        mergeSort(nums)
        return self.count

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        minValue = prices[0]
        res = 0
        for i in range(1, len(prices)):
            minValue = min(minValue, prices[i])
            res = max(res, prices[i]-minValue)
        return res

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # 使用快速排序
        lo = 0
        hi = len(nums) - 1
        k = len(nums) - k
        while lo <= hi:
            p = self.partition(nums, lo, hi)
            if p > k:
                hi = p - 1
            elif p < k:
                lo = p + 1
            else:
                return nums[p]
        return -1
    
    def  partition(self, nums, lo, hi):
        pivot = nums[lo]
        i = lo
        j = hi
        while i < j:
            while i < j and nums[j] >= pivot:
                j -= 1
            nums[i] = nums[j]
            while i < j and nums[i] < pivot:
                i += 1
            nums[j] = nums[i]
        nums[i] = pivot
        return i

def partition(nums, lo, hi):
    pivot = nums[lo]
    i = lo
    j = hi
    while i < j:
        while i < j and nums[j] >= pivot:
            j -= 1
        nums[i] = nums[j]
        while i < j and nums[i] < pivot:
            i += 1
        nums[j] = nums[i]
    nums[i] = pivot
    return i
def getKminnums(nums, k):
    index = k - 1
    low = 0
    high = len(nums) - 1
    while low <= high:
        p = partition(nums, low, high)
        if p > index:
            high = p - 1
        elif p < index:
            low = p + 1
        else:
            # 输出前k个元素
            return nums[:index+1]