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"]。
nums 中第 4 大的整数是 "3"。

示例 2：

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

示例 3：

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

约束条件：

  • 1 <= k <= nums.length <= 10^4
  • 1 <= nums[i].length <= 100
  • nums[i] 仅由数字组成
  • nums[i] 不含前导零

提示：

  • 如果两个数字的长度不同，哪一个更大？
  • 较长的数字较大。
  • 如果两个数字的长度相同，哪一个更大？
  • 从最高位开始比较两个数字。一旦找到第一个不同的数字，拥有较大数字的那个就是较大的数。

解题思路

解题思路

这道题的关键在于如何比较字符串形式的大整数。主要有以下几种解法：

方法一：自定义排序（推荐）

由于数字可能非常大（最多100位），不能直接转换为整数。我们需要自定义比较函数：

  1. 首先比较字符串长度，长度更长的数字更大
  2. 如果长度相同，按字典序比较

方法二：堆（优先队列）

使用最小堆维护前k个最大的数字，最终堆顶就是第k大的数字。

方法三：快速选择

类似快排的思想，平均时间复杂度为O(n)，但实现相对复杂。

考虑到题目约束和实现简洁性，推荐使用自定义排序的方法。我们定义一个比较函数，然后对数组进行降序排序，取第k-1个元素即可。

比较函数的逻辑：

  • 如果a的长度大于b，则a > b
  • 如果长度相等，直接比较字符串的字典序
  • 返回结果用于降序排序

代码实现

class Solution {
public:
    string kthLargestNumber(vector<string>& nums, int k) {
        sort(nums.begin(), nums.end(), [](const string& a, const string& b) {
            if (a.length() != b.length()) {
                return a.length() > b.length();
            }
            return a > b;
        });
        return nums[k - 1];
    }
};

class Solution:
    def kthLargestNumber(self, nums: List[str], k: int) -> str:
        def compare(a, b):
            if len(a) != len(b):
                return len(b) - len(a)
            if a < b:
                return 1
            elif a > b:
                return -1
            else:
                return 0
        
        from functools import cmp_to_key
        nums.sort(key=cmp_to_key(compare))
        return nums[k - 1]

public class Solution {
    public string KthLargestNumber(string[] nums, int k) {
        Array.Sort(nums, (a, b) => {
            if (a.Length != b.Length) {
                return b.Length.CompareTo(a.Length);
            }
            return b.CompareTo(a);
        });
        return nums[k - 1];
    }
}

var kthLargestNumber = function(nums, k) {
    nums.sort((a, b) => {
        if (a.length !== b.length) {
            return b.length - a.length;
        }
        return b.localeCompare(a);
    });
    return nums[k - 1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度排序解法
时间复杂度O(n log n × m)
空间复杂度O(1)

其中 n 是数组长度，m 是字符串的平均长度。时间复杂度主要由排序决定，字符串比较的时间复杂度为 O(m)。

相关题目