day2:215. 数组中的第K个最大元素快速排序 python代码

爱被打了一巴掌 2022-12-04 09:12 72阅读 0赞

"""
    快速排序
    思想： 
    基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，
    其中一部分的所有数据都比另外一部分的所有数据都要小，
    然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，
    以此达到整个数据变成有序序列。
    
    """
    
    # 方法1： 递归
    def partition(arr, first, end):
        i, j = first, end
        while i < j:
            while i < j and arr[i] <= arr[j]:
                j = j - 1
            if i < j:
                # 交换
                temp = arr[j]
                arr[j] = arr[i]
                arr[i] = temp
                i = i + 1
    
            while i < j and arr[i] <= arr[j]:
                i = i + 1
            if i < j:
                # 交换
                temp = arr[j]
                arr[j] = arr[i]
                arr[i] = temp
                j = j - 1
                
        return i
    
    
    # 数据发生了变化； 不用返回
    def quicksort(arr, low, heigh):
        # print(arr)
        if low < heigh:
            i = partition(arr, low, heigh)
            quicksort(arr, low, i-1)
            quicksort(arr, i+1, heigh)
    
    
    # 快速排序 不用设定 返回值；
    arr = [10, 7, 8, 9, 1, 5]
    n = len(arr)
    
    print("0:")
    print(arr)
    quicksort(arr, 0, n-1)
    print(arr)
    
    print("1:")
    value = [23, 13, 49, 6, 31, 19, 28]
    print(value)
    quicksort(value, 0, len(value) - 1)
    print(value)

[215. 数组中的第K个最大元素][215. _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:

class Solution:
        def findKthLargest(self, nums: List[int], k: int) -> int:
            nums = sorted(nums)
            return nums[-k]

解法2:

class Solution:
        def findKthLargest(self, nums: List[int], k: int) -> int:
            
            # 使用快速排序算法
            quicksort(nums, 0, len(nums)-1)
            return nums[-k]

[4. 寻找两个正序数组的中位数][4.]

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

**示例 1:**

nums1 = [1, 3]
    nums2 = [2]
     
    则中位数是 2.0

**示例 2:**

nums1 = [1, 2]
    nums2 = [3, 4]
     
    则中位数是 (2 + 3)/2 = 2.5

**方法1:**

class Solution:
        def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
            # 中位数 ； 中间的数， 个数为奇数： 中间的数， 为偶数： 中间两个相加/2
            # 理解 记住  
            # 寻找 第k小(第k大)元素问题 的解法
            def findKthElement(arr1, arr2, k):
                len1, len2 = len(arr1), len(arr2)
                if len1 > len2:  # 第一参数 数组长度长
                    return findKthElement(arr2, arr1, k)
                if not arr1:  # arr1 为null
                    return arr2[k-1]   # 第k个即为目标
                if k == 1:
                    return min(arr1[0], arr2[0])
                # k值减小 ， 去掉 前k/2个元素
                i, j = min(k//2, len1)-1, min(k//2, len2)-1
                if arr1[i] > arr2[j]:
                    # 说明第k小元素 不再arr[:j]中, k 值发生变化
                    return findKthElement(arr1, arr2[j+1:], k-j-1)
                else:
                    return findKthElement(arr1[i+1:], arr2, k-i-1)
     
            l1, l2 = len(nums1), len(nums2)
            # 寻找中位数，相当于 寻找 两个 第 k 小问题 【】
            # 若为 偶数： 寻找 两个不同位置 （4+4+1）//2 = 4， （4+4+2）//2=5；
            # 若为 奇数： 寻找 两个相同位置 （4+3+1）//2=4， （4+3+2）// 2=4；
            left, right = (l1+l2+1) // 2, (l1+l2+2) // 2
            return (findKthElement(nums1, nums2, left) + findKthElement(nums1, nums2, right)) / 2

**寻找两个正序数组中第k小 数值：**

# 寻找 第k小元素问题 的解法
    def findKthElement(arr1, arr2, k):
        len1, len2 = len(arr1), len(arr2)
        if len1 > len2:  # 第一参数  数组短的放前面
            return findKthElement(arr2, arr1, k)
        if not arr1:  # arr1 为null
            return arr2[k - 1]  # 第k个即为目标
        if k == 1:
            return min(arr1[0], arr2[0])
        # k值减小 ， 去掉 前k/2个元素
        i, j = min(k // 2, len1) - 1, min(k // 2, len2) - 1
        if arr1[i] > arr2[j]:
            # 说明第k小元素 不再arr[:j]中, k 值发生变化
            return findKthElement(arr1, arr2[j + 1:], k - j - 1)
        else:
            return findKthElement(arr1[i + 1:], arr2, k - i - 1)

寻找两个正序数组中第k大数值：

这个可以利用求第k小 的算法， 求 第 n大， 相当与 求 ( 两个数组长度之和 - n + 1)小元素；

big = 5 # 第三大 即第 all_len - big + 1 小
    a = [3, 4, 5, 6, 6]
    b = [10, 34, 35, 36, 37, 38]
    find_value = findKthElement(a, b, (len(a)+len(b)) - big + 1)
    print(find_value) # 34

[215. _K]: https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
[4.]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/