找出数组中的第 K 大整数

标签: 数组 字符串 分治 快速选择 排序 堆（优先队列）

难度: Medium

给你一个字符串数组 nums 和一个整数 k 。nums 中的每个字符串都表示一个不含前导零的整数。

返回 nums 中表示第 k 大整数的字符串。

注意：重复的数字在统计时会视为不同元素考虑。例如，如果 nums 是 ["1","2","2"]，那么 "2" 是最大的整数，"2" 是第二大的整数，"1" 是第三大的整数。

示例 1：

输入：nums = ["3","6","7","10"], k = 4
输出："3"
解释：
nums 中的数字按非递减顺序排列为 ["3","6","7","10"]
其中第 4 大整数是 "3"

示例 2：

输入：nums = ["2","21","12","1"], k = 3
输出："2"
解释：
nums 中的数字按非递减顺序排列为 ["1","2","12","21"]
其中第 3 大整数是 "2"

示例 3：

输入：nums = ["0","0"], k = 2
输出："0"
解释：
nums 中的数字按非递减顺序排列为 ["0","0"]
其中第 2 大整数是 "0"

提示：

  • 1 <= k <= nums.length <= 104
  • 1 <= nums[i].length <= 100
  • nums[i] 仅由数字组成
  • nums[i] 不含任何前导零

Submission

运行时间: 54 ms

内存: 22.9 MB

class Solution:
    def kthLargestNumber(self, nums: List[str], k: int) -> str:
        nums = [int(num) for num in nums]
        n = len(nums)
        low,high = 0,n-1
        while(low <= high):
            small,equal,bigger = [],[],[]
            pivot = random.choice(nums)
            for num in nums:
                if num > pivot:
                    bigger.append(num)
                elif num == pivot:
                    equal.append(num)
                else:
                    small.append(num)
            # print(pivot,bigger,equal,small,k)
            if len(bigger) >= k:
                high = len(bigger)-1
                nums = bigger
            elif len(bigger) + len(equal) >= k:
                return str(equal[0])
            else:
                high = len(small)-1
                nums = small
                k = k - len(bigger) - len(equal)

Explain

此题解使用了快速选择算法来解决问题。首先，将字符串数组转换为整数数组以便比较大小。快速选择是一种类似于快速排序的算法，目的是找到第k大的元素而不完全排序整个数组。算法的核心是通过不断选择一个'pivot'元素，并将数组分为三个部分：比pivot大的，等于pivot的和比pivot小的。根据这三个部分的大小，可以决定下一步搜索的方向（大的一边或小的一边），直到找到第k大的元素。在每次迭代中，我们可以缩小搜索范围，这样可以较快地找到答案。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def kthLargestNumber(self, nums: List[str], k: int) -> str:
        nums = [int(num) for num in nums]  # 将字符串数组转换为整数数组
        n = len(nums)
        low, high = 0, n-1
        while(low <= high):
            small, equal, bigger = [], [], []
            pivot = random.choice(nums)  # 随机选择一个pivot
            for num in nums:
                if num > pivot:
                    bigger.append(num)
                elif num == pivot:
                    equal.append(num)
                else:
                    small.append(num)
            # 根据bigger, equal, small的大小决定下一步搜索方向
            if len(bigger) >= k:
                high = len(bigger)-1
                nums = bigger
            elif len(bigger) + len(equal) >= k:
                return str(equal[0])  # 找到第k大元素
            else:
                high = len(small)-1
                nums = small
                k = k - len(bigger) - len(equal)  # 更新k的值，准备下一轮搜索

Explore

在题解中，将字符串数组转换为整数数组时确实使用了int()函数进行转换，这样确实可能在某些情况下遇到非常大的整数值，导致整数溢出或性能问题。在Python中，int类型理论上能够处理任意大小的整数，不过这将会消耗更多的内存和可能影响性能。因此，在实际应用中可能需要考虑到这个问题，特别是在处理非常大的数据集或者在内存受限的环境下。

在快速选择算法中，当'equal'数组的长度加上'bigger'数组的长度正好等于k时，返回'equal[0]'是因为所有比'equal[0]'大的数已经在'bigger'数组中，且它们的数量加上'equal'中的任意一个元素总数恰好是k。这意味着'equal[0]'就是第k大的元素。此外，由于所有'equal'数组的元素值都相同，因此选择任何一个元素作为答案都是正确的。

在题解中所描述的算法实际上是使用迭代而不是递归实现的。因此，不会因递归调用而导致栈溢出的问题。即使在一些递归版本的快速选择算法中，通常情况下递归的深度不会非常深，因为每次递归调用都会排除掉一部分元素。然而，在最坏的情况下，如果数据分布不均匀，递归深度可能会比较深，这在理论上是可能导致栈溢出的，尤其是在栈大小非常有限的环境中。