列表

详情

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

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

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

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

提示：

 

示例 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 。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: vector<int> smallestTrimmedNumbers(vector<string>& nums, vector<vector<int>>& queries) { } };

golang 解法, 执行用时: 396 ms, 内存消耗: 7.1 MB, 提交时间: 2023-10-10 16:12:55 

func smallestTrimmedNumbers1(nums []string, queries [][]int) []int {
	ans := make([]int, len(queries))
	type pair struct { s string; i int }
	ps := make([]pair, len(nums))
	for i, q := range queries {
		for j, s := range nums {
			ps[j] = pair{s[len(s)-q[1]:], j}
		}
		// 也可以用稳定排序，但是要慢一些 sort.SliceStable(ps, func(i, j int) bool { return ps[i].s < ps[j].s })
		sort.Slice(ps, func(i, j int) bool { a, b := ps[i], ps[j]; return a.s < b.s || a.s == b.s && a.i < b.i })
		ans[i] = ps[q[0]-1].i
	}
	return ans
}


func smallestTrimmedNumbers(nums []string, queries [][]int) (ans []int) {
	for i, q := range queries {
		q[0] |= i << 32 // 把询问的下标整合到 k 里面，相比 append 到 q 里面可以避免扩容
	}
	sort.Slice(queries, func(i, j int) bool { return queries[i][1] < queries[j][1] }) // 按 trim 排序

	m := len(nums[0])
	type pair struct { s string; i int }
	ps := make([]pair, len(nums))
	for i, s := range nums {
		ps[i] = pair{s, i}
	}

	ans = make([]int, len(queries))
	p := 1
	for _, q := range queries {
		for ; p <= q[1]; p++ {
			sort.SliceStable(ps, func(i, j int) bool { return ps[i].s[m-p] < ps[j].s[m-p] }) // 只比较第 m-p 个字符的大小
		}
		ans[q[0]>>32] = ps[q[0]&math.MaxUint32-1].i
	}
	return
}

cpp 解法, 执行用时: 352 ms, 内存消耗: 32.6 MB, 提交时间: 2023-10-10 16:12:21 

class Solution {
public:
    vector<int> smallestTrimmedNumbers(vector<string> &nums, vector<vector<int>> &queries) {
        vector<int> ans(queries.size());
        int n = nums.size(), m = nums[0].length();
        int idx[n];
        for (int i = 0; i < queries.size(); ++i) {
            auto &q = queries[i];
            iota(idx, idx + n, 0);
            stable_sort(idx, idx + n, [&](int a, int b) {
                auto &s = nums[a], &t = nums[b];
                for (int j = m - q[1]; j < m; ++j)
                    if (s[j] != t[j]) return s[j] < t[j];
                return false;
            });
            ans[i] = idx[q[0] - 1];
        }
        return ans;
    }

    vector<int> smallestTrimmedNumbers2(vector<string> &nums, vector<vector<int>> &queries) {
        int nq = queries.size();
        int qid[nq];
        iota(qid, qid + nq, 0);
        sort(qid, qid + nq, [&](int a, int b) { return queries[a][1] < queries[b][1]; });

        int n = nums.size(), m = nums[0].length();
        int idx[n];
        iota(idx, idx + n, 0);

        vector<int> ans(nq);
        int p = 1;
        for (int qi : qid) {
            auto &q = queries[qi];
            for (; p <= q[1]; ++p)
                stable_sort(idx, idx + n, [&](int a, int b) { return nums[a][m - p] < nums[b][m - p]; });
            ans[qi] = idx[q[0] - 1];
        }
        return ans;
    }
};

java 解法, 执行用时: 183 ms, 内存消耗: 43.3 MB, 提交时间: 2023-10-10 16:11:43 

class Solution {
    // 直接排序
    public int[] smallestTrimmedNumbers1(String[] nums, int[][] queries) {
        var ans = new int[queries.length];
        var m = nums[0].length();
        for (var p = 0; p < queries.length; p++) {
            var q = queries[p];
            var idx = new ArrayList<>(Arrays.asList(IntStream.range(0, nums.length).boxed().toArray(Integer[]::new)));
            Collections.sort(idx, (i, j) -> nums[i].substring(m - q[1]).compareTo(nums[j].substring(m - q[1]))); // 稳定排序
            ans[p] = idx.get(q[0] - 1);
        }
        return ans;
    }
    
    // 离线 + 增量排序
    public int[] smallestTrimmedNumbers(String[] nums, int[][] queries) {
        var qid = IntStream.range(0, queries.length).boxed().toArray(Integer[]::new);
        Arrays.sort(qid, (i, j) -> queries[i][1] - queries[j][1]);

        var m = nums[0].length();
        var idx = new ArrayList<>(Arrays.asList(IntStream.range(0, nums.length).boxed().toArray(Integer[]::new)));

        var ans = new int[queries.length];
        var p = 1;
        for (var qi : qid) {
            var q = queries[qi];
            while (p <= q[1]) {
                final var pp = p++;
                Collections.sort(idx, (i, j) -> nums[i].charAt(m - pp) - nums[j].charAt(m - pp)); // 稳定排序
            }
            ans[qi] = idx.get(q[0] - 1);
        }
        return ans;
    }
}

python3 解法, 执行用时: 416 ms, 内存消耗: 16.1 MB, 提交时间: 2023-10-10 16:10:33 

class Solution:
    # 直接排序，对每个询问，按照题目要求排序，取第 k 小的元素的下标。
    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:
        return [sorted((s[-trim:], i) for i, s in enumerate(nums))[k - 1][1] for k, trim in queries]

    # 离线 + 增量排序
    def smallestTrimmedNumbers2(self, nums: List[str], queries: List[List[int]]) -> List[int]:
        idx = list(range(len(nums)))
        ans, j = [0] * len(queries), 1
        for qi, (k, trim) in sorted(enumerate(queries), key=lambda q: q[1][1]):  # 按 trim 排序
            while j <= trim:
                idx.sort(key=lambda i: nums[i][-j])  # 只比较倒数第 j 个字符的大小
                j += 1
            ans[qi] = idx[k - 1]
        return ans

上一题

© 2024 leetcode.cn