Medium

题目描述

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

对于每个 queries[i]，你需要找到 x 在 nums 数组中第 queries[i] 次出现的索引。如果 x 的出现次数少于 queries[i] 次，则该查询的答案应该是 -1。

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

示例 1：

输入：nums = [1,3,1,7], queries = [1,3,2,4], x = 1
输出：[0,-1,2,-1]
解释：
- 第 1 个查询，1 的第 1 次出现在索引 0。
- 第 2 个查询，nums 中只有两次出现 1，所以答案是 -1。
- 第 3 个查询，1 的第 2 次出现在索引 2。
- 第 4 个查询，nums 中只有两次出现 1，所以答案是 -1。

示例 2：

输入：nums = [1,2,3], queries = [10], x = 5
输出：[-1]
解释：
- 第 1 个查询，5 在 nums 中不存在，所以答案是 -1。

约束条件：

  • 1 <= nums.length, queries.length <= 10^5
  • 1 <= queries[i] <= 10^5
  • 1 <= nums[i], x <= 10^4

提示：

  • 压缩数组 nums 并将每个元素的所有出现位置保存在单独的数组中。

解题思路

这道题的核心思想是预处理，将目标元素 x 在数组中的所有出现位置记录下来，然后对每个查询进行快速查找。

解题思路：

  1. 预处理阶段：遍历 nums 数组，找到所有值等于 x 的索引位置，并按顺序存储在一个列表中。这样我们就得到了 x 的所有出现位置的有序列表。

  2. 查询阶段：对于每个查询 queries[i]，我们需要找到 x 的第 queries[i] 次出现的索引。由于我们已经预处理了所有出现位置，只需要检查：

    • 如果 queries[i] 大于出现次数，返回 -1
    • 否则返回第 queries[i]-1 个位置（因为数组索引从0开始）

算法优势：

  • 时间复杂度优化：预处理一次后，每次查询都是 O(1) 的时间复杂度
  • 空间换时间：使用额外的数组存储位置信息，避免重复遍历

这种方法特别适合多次查询的场景，因为预处理的成本可以在多次查询中摊销。

代码实现

class Solution {
public:
    vector<int> occurrencesOfElement(vector<int>& nums, vector<int>& queries, int x) {
        vector<int> positions;
        
        // 预处理：找到所有x出现的位置
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == x) {
                positions.push_back(i);
            }
        }
        
        vector<int> result;
        // 处理每个查询
        for (int query : queries) {
            if (query > positions.size()) {
                result.push_back(-1);
            } else {
                result.push_back(positions[query - 1]);
            }
        }
        
        return result;
    }
};

class Solution:
    def occurrencesOfElement(self, nums: List[int], queries: List[int], x: int) -> List[int]:
        # 预处理：找到所有x出现的位置
        positions = []
        for i, num in enumerate(nums):
            if num == x:
                positions.append(i)
        
        result = []
        # 处理每个查询
        for query in queries:
            if query > len(positions):
                result.append(-1)
            else:
                result.append(positions[query - 1])
        
        return result

public class Solution {
    public int[] OccurrencesOfElement(int[] nums, int[] queries, int x) {
        List<int> positions = new List<int>();
        
        // 预处理：找到所有x出现的位置
        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] == x) {
                positions.Add(i);
            }
        }
        
        int[] result = new int[queries.Length];
        // 处理每个查询
        for (int i = 0; i < queries.Length; i++) {
            if (queries[i] > positions.Count) {
                result[i] = -1;
            } else {
                result[i] = positions[queries[i] - 1];
            }
        }
        
        return result;
    }
}

var occurrencesOfElement = function(nums, queries, x) {
    const positions = [];
    
    // 预处理：找到所有x出现的位置
    for (let i = 0; i < nums.length; i++) {
        if (nums[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + m)n 为 nums 长度，m 为 queries 长度。预处理需要 O(n)，处理查询需要 O(m)
空间复杂度O(k)k 为元素 x 在 nums 中的出现次数，用于存储位置信息