Question

2343. Query Kth Smallest Trimmed Number

中文文档

Description

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.

Example 2:

Input: nums = ["24","37","96","04"], queries = [[2,1],[2,2]]
Output: [3,0]
Explanation:
1. Trimmed to the last digit, nums = ["4","7","6","4"]. The 2nd smallest number is 4 at index 3.
   There are two occurrences of 4, but the one at index 0 is considered smaller than the one at index 3.
2. Trimmed to the last 2 digits, nums is unchanged. The 2nd smallest number is 24.

 

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

 

Follow up: Could you use the Radix Sort Algorithm to solve this problem? What will be the complexity of that solution?

Solutions

Solution 1

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

class Solution {
  public int[] smallestTrimmedNumbers(String[] nums, int[][] queries) {
    int n = nums.length;
    int m = queries.length;
    int[] ans = new int[m];
    String[][] t = new String[n][2];
    for (int i = 0; i < m; ++i) {
      int k = queries[i][0], trim = queries[i][1];
      for (int j = 0; j < n; ++j) {
        t[j] = new String[] {nums[j].substring(nums[j].length() - trim), String.valueOf(j)};
      }
      Arrays.sort(t, (a, b) -> {
        int x = a[0].compareTo(b[0]);
        return x == 0 ? Long.compare(Integer.valueOf(a[1]), Integer.valueOf(b[1])) : x;
      });
      ans[i] = Integer.valueOf(t[k - 1][1]);
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> smallestTrimmedNumbers(vector<string>& nums, vector<vector<int>>& queries) {
    int n = nums.size();
    vector<pair<string, int>> t(n);
    vector<int> ans;
    for (auto& q : queries) {
      int k = q[0], trim = q[1];
      for (int j = 0; j < n; ++j) {
        t[j] = {nums[j].substr(nums[j].size() - trim), j};
      }
      sort(t.begin(), t.end());
      ans.push_back(t[k - 1].second);
    }
    return ans;
  }
};

func smallestTrimmedNumbers(nums []string, queries [][]int) []int {
  type pair struct {
    s string
    i int
  }
  ans := make([]int, len(queries))
  t := make([]pair, len(nums))
  for i, q := range queries {
    for j, s := range nums {
      t[j] = pair{s[len(s)-q[1]:], j}
    }
    sort.Slice(t, func(i, j int) bool { a, b := t[i], t[j]; return a.s < b.s || a.s == b.s && a.i < b.i })
    ans[i] = t[q[0]-1].i
  }
  return ans
}