Question
You are given a 0-indexed array of strings nums, where each string is of equal length and consists of only digits.
You are also given a 0-indexed 2D integer array queries where queries[i] = [ki, trimi]. For each queries[i], you need to:
•
Trim each number in nums to its rightmost trimi digits.
•
Determine the index of the kith smallest trimmed number in nums. If two trimmed numbers are equal, the number with the lower index is considered to be smaller.
•
Reset each number in nums to its original length.
Return an array answer of the same length as queries, where answer[i] is the answer to the ith query.
Note:
•
To trim to the rightmost x digits means to keep removing the leftmost digit, until only x digits remain.
•
Strings in nums may contain leading zeros.
Example 1:
Input: nums = ["102","473","251","814"], queries = [[1,1],[2,3],[4,2],[1,2]]
Output: [2,2,1,0]
Explanation:
1. After trimming to the last digit, nums = ["2","3","1","4"].
The smallest number is 1 at index 2.
2. Trimmed to the last 3 digits, nums is unchanged.
The 2nd smallest number is 251 at index 2.
3. Trimmed to the last 2 digits, nums = ["02","73","51","14"].
The 4th smallest number is 73.
4. Trimmed to the last 2 digits, the smallest number is 2 at index 0.
Note that the trimmed number "02" is evaluated as 2.
Plain Text
복사
Constraints:
•
1 <= nums.length <= 100
•
1 <= nums[i].length <= 100
•
nums[i] consists of only digits.
•
All nums[i].length are equal.
•
1 <= queries.length <= 100
•
queries[i].length == 2
•
1 <= ki <= nums.length
•
1 <= trimi <= nums[i].length
My Answer
class Solution:
def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:
answer = []
for k, trim in queries:
trimmed = [(num[-trim:], idx) for idx, num in enumerate(nums)]
trimmed.sort()
answer.append(trimmed[k-1][1])
return answer
Python
복사
시간복잡도: O(NlogN)
Optimized Version
class Solution:
def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:
from collections import defaultdict
n = len(nums)
trim_to_sorted = dict()
needed_trims = set(trim for _, trim in queries)
for trim in needed_trims:
trimmed = [(num[-trim:], idx) for idx, num in enumerate(nums)]
trimmed.sort()
trim_to_sorted[trim] = trimmed
answer = []
for k, trim in queries:
answer.append(trim_to_sorted[trim][k-1][1])
return answer
Python
복사
•
needed_trims로 실제 필요한 trim값만 한 번씩만 처리
•
trim_to_sorted[trim]에는 해당 trim 값에 대해 사전순 + 인덱스순 정렬된 결과를 저장
•
각 쿼리마다 바로 꺼내서 결과를 만듦
