# 分治排序算法扩展

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]