【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. $1\le nums.length,queries.length\le 10^5$
2. $1\le queries[i]\le 10^5$
3. $1\le nums[i],x\le 10^4$

思路

1. 处理查询之前的预处理：
   为了能快速回答每个查询，我们可以预先遍历数组 $nums$，记录所有出现 $x$ 的下标。将所有这些下标存储在一个数组 $arr$ 中。

2. 处理每个查询：
   对于每个查询 $queries[i]$，如果 $queries[i]$ 大于数组 $arr$ 的长度，则返回 $-1$，表示没有足够的 $x$ 出现。否则返回 $arr[queries[i]-1]$，即第 $queries[i]$ 个 $x$ 的下标。

代码

class Solution {
public:
    vector<int> occurrencesOfElement(vector<int>& nums, vector<int>& queries, int x) {
        vector<int> arr;
        vector<int> answer;
        for(int i = 0; i < nums.size(); ++i)
        {
            if(nums[i] == x)
            {
                arr.push_back(i);
            }
        }
        for(int i = 0; i < queries.size(); ++i)
        {
            if(queries[i] > arr.size())answer.push_back(-1);
            else answer.push_back(arr[queries[i]-1]);
            
        }
        return answer;
    }
};

复杂度分析

时间复杂度

1. 预处理部分：
   我们遍历 $nums$ 一次，寻找所有出现 $x$ 的位置，时间复杂度为 $O(n)$，其中 $n$ 是数组 $nums$ 的长度。

2. 查询部分：
   对于每个查询，我们访问 $arr$ 数组，查找第 $queries[i]$ 个 $x$ 的下标，这个操作的时间复杂度为 $O(1)$。因此，处理所有查询的时间复杂度是 $O(q)$，其中 $q$ 是查询数组 $queries$ 的长度。

总时间复杂度为 $O(n+q)$，其中 $n$ 是 $nums$ 数组的长度，$q$ 是查询数组 $queries$ 的长度。

空间复杂度

额外使用了一个数组 $arr$ 来存储 $x$ 的所有下标，空间复杂度是 $O(n)$，其中 $n$ 是 $nums$ 数组的长度。

结果

总结

通过预处理来加速查询，先遍历一遍 $nums$ 数组，找出所有 $x$ 出现的位置，然后对每个查询进行常数时间的处理