[LeetCode] 每日一题 3159. 查询数组中元素的出现位置

题目链接

题目描述

给你一个整数数组 nums ，一个整数数组 queries 和一个整数 x 。

对于每个查询 queries[i] ，你需要找到 nums 中第 queries[i] 个 x 的位置，并返回它的下标。如果数组中 x 的出现次数少于 queries[i] ，该查询的答案为 -1 。

请你返回一个整数数组 answer ，包含所有查询的答案。

示例输入

示例 1

输入：nums = [1,3,1,7], queries = [1,3,2,4], x = 1

输出：[0,-1,2,-1]

解释：
第 1 个查询，第一个 1 出现在下标 0 处。
第 2 个查询，nums 中只有两个 1 ，所以答案为 -1 。
第 3 个查询，第二个 1 出现在下标 2 处。
第 4 个查询，nums 中只有两个 1 ，所以答案为 -1 。

示例 2

输入：nums = [1,2,3], queries = [10], x = 5

输出：[-1]

解释：
第 1 个查询，nums 中没有 5 ，所以答案为 -1 。

提示

• 1 <= nums.length, queries.length <= 10^5

• 1 <= queries[i] <= 10^5

• 1 <= nums[i], x <= 10^4

题解

解题思路

1. 预处理：

   • 遍历数组 nums，记录所有等于 x 的元素的下标，将它们存入一个列表 xIndex 中

   • 这样可以快速定位每个 x 的位置

2. 查询处理：

   • 对于每个查询 queries[i]，取出第 queries[i] 个 x 的下标，具体为 xIndex[queries[i] - 1]

   • 如果 queries[i] > xIndex.size()，说明 nums 中 x 的出现次数少于 queries[i]，返回 -1

3. 优化：

   • 将查询的结果直接修改在 queries 数组上，节省额外空间

代码实现

class Solution {
    public int[] occurrencesOfElement(int[] nums, int[] queries, int x) {
        // 1. 收集所有等于 x 的元素下标
        List<Integer> xIndex = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == x) {
                xIndex.add(i);
            }
        }

        // 2. 处理每个查询
        for (int i = 0; i < queries.length; i++) {
            int cnt = queries[i];
            if (cnt - 1 >= xIndex.size()) {
                queries[i] = -1; // 超出范围，返回 -1
            } else {
                queries[i] = xIndex.get(cnt - 1); // 返回下标
            }
        }

        return queries;
    }
}

复杂度分析

1. 时间复杂度：

2. 预处理：遍历数组 nums，时间复杂度为 O(n)，其中 n 是数组 nums 的长度

   • 查询处理：遍历 queries，每次查询是常数时间 O(1)，因此时间复杂度为 O(m)，其中 m 是数组 queries 的长度

   • 总时间复杂度为 O(n+m)

3. 空间复杂度：

   • 额外空间为存储下标的列表 xIndex，其最大大小为 O(k)，其中 k 是 nums 中 x 的出现次数

   • 查询结果直接修改在原数组 queries 上，不需要额外空间

   • 总空间复杂度为 O(k)

总结

• 通过预处理存储目标元素的下标，可以高效处理多次查询，降低每次查询的时间复杂度

• 本题的关键在于分清预处理和查询的职责，通过分离两者使代码更清晰且易于维护

• 算法复杂度适中，适合大规模数据的处理

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。