What is the best approach for solving Query Kth Smallest Trimmed Number?

The best approach involves either sorting the list after trimming each string or using Quickselect to find the Kth smallest element efficiently without fully sorting the array.

How do you handle tie-breaking in the Kth smallest query?

Tie-breaking is handled by considering the original index of the elements in `nums` after they have been trimmed and evaluated as integers.

Can Radix Sort be useful for this problem?

Yes, Radix Sort can be helpful when strings are of equal length, allowing you to sort the numbers efficiently without comparing all characters at once.

What is the time complexity of the brute force approach?

The brute force approach has a time complexity of O(N * log N) due to the sorting operation for each query, where N is the length of the array.

How can GhostInterview help me with this problem?

GhostInterview provides insights into optimizing string manipulations and helps choose the most efficient algorithm for handling trimming and sorting operations in this problem.

#2343

Medium

auto_awesome数组·string

LeetCode 题解工作台

裁剪数字后查询第 K 小的数字

给你一个下标从 0 开始的字符串数组 nums ，其中每个字符串长度相等且只包含数字。再给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [k i , trim i ] 。对于每个 queries[i] ，你需要：将 nums 中每个数字裁剪到剩下…

数组字符串分治排序堆（优先队列）

题目描述

给你一个下标从 0 开始的字符串数组 nums ，其中每个字符串 长度相等 且只包含数字。

再给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [k_i, trim_i] 。对于每个 queries[i] ，你需要：

将 nums 中每个数字裁剪到剩下 最右边 trim_i 个数位。
在裁剪过后的数字中，找到 nums 中第 k_i 小数字对应的下标。如果两个裁剪后数字一样大，那么下标更小的数字视为更小的数字。
将 nums 中每个数字恢复到原本字符串。

请你返回一个长度与 queries 相等的数组 answer，其中 answer[i]是第 i 次查询的结果。

提示：

裁剪到剩下最右边 x 个数位的意思是不断删除最左边的数位，直到剩下 x 个数位。
nums 中的字符串可能会有前导 0 。

示例 1：

输入：nums = ["102","473","251","814"], queries = [[1,1],[2,3],[4,2],[1,2]]
输出：[2,2,1,0]
解释：
1. 裁剪到只剩 1 个数位后，nums = ["2","3","1","4"] 。最小的数字是 1 ，下标为 2 。
2. 裁剪到剩 3 个数位后，nums 没有变化。第 2 小的数字是 251 ，下标为 2 。
3. 裁剪到剩 2 个数位后，nums = ["02","73","51","14"] 。第 4 小的数字是 73 ，下标为 1 。
4. 裁剪到剩 2 个数位后，最小数字是 2 ，下标为 0 。
   注意，裁剪后数字 "02" 值为 2 。

示例 2：

输入：nums = ["24","37","96","04"], queries = [[2,1],[2,2]]
输出：[3,0]
解释：
1. 裁剪到剩 1 个数位，nums = ["4","7","6","4"] 。第 2 小的数字是 4 ，下标为 3 。
   有两个 4 ，下标为 0 的 4 视为小于下标为 3 的 4 。
2. 裁剪到剩 2 个数位，nums 不变。第二小的数字是 24 ，下标为 0 。

提示：

1 <= nums.length <= 100
1 <= nums[i].length <= 100
nums[i] 只包含数字。
所有 nums[i].length 的长度相同。
1 <= queries.length <= 100
queries[i].length == 2
1 <= k_i <= nums.length
1 <= trim_i <= nums[0].length

进阶：你能使用 基数排序算法 解决此问题吗？这种解法的复杂度又是多少？

lightbulb

解题思路

方法一：模拟

根据题意，我们可以模拟裁剪过程，然后对裁剪后的字符串进行排序，最后根据下标找到对应的数字即可。

时间复杂度 $O(m \times \ n \times \log n \times s)$ ，空间复杂度 $O(n)$ 。其中 $m$ 和 $n$ 分别为 $\textit{nums}$ 和 $\textit{queries}$ 的长度，而 $s$ 为 $\textit{nums}[i]$ 字符串的长度。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def smallestTrimmedNumbers(
        self, nums: List[str], queries: List[List[int]]
    ) -> List[int]:
        ans = []
        for k, trim in queries:
            t = sorted((v[-trim:], i) for i, v in enumerate(nums))
            ans.append(t[k - 1][1])
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Testing the candidate's ability to optimize for multiple queries over a shared data set.
question_mark
Looking for an efficient implementation that handles trimming and sorting without unnecessary recalculations.
question_mark
Assesses familiarity with sorting algorithms like Quickselect and Radix Sort, especially in the context of numeric strings.

warning

常见陷阱

外企场景

error
Not optimizing the trimming and sorting process, leading to excessive time complexity in handling multiple queries.
error
Incorrectly handling tie-breaking in the case of equal trimmed numbers, potentially returning wrong indices.
error
Forgetting to account for trimming from the end of the string and misinterpreting the query's requirement.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to handle unsorted input strings that need to be sorted based on trimming and queries.
arrow_right_alt
Alter the problem to use a custom comparison function when sorting the trimmed numbers.
arrow_right_alt
Consider adding constraints where strings are not of equal length, which requires extra handling during the trimming process.

help

常见问题

外企场景

继续练习

#1985 找出数组中的第 K 大整数 #1738 找出第 K 大的异或坐标值 #2456 最流行的视频创作者