3159 查询数组中元素的出现位置

· 2024-12-27   · 次阅读   · 字数统计: 180字   · 阅读时长≈ 1分钟

  · 算法题解   · LeetCode

题目链接

3159. 查询数组中元素的出现位置

分析

哈希表

遍历数组，使用哈希表记录每一个 $x$ 出现位置的下标

对于每次询问，如果超过哈希表长度则答案为 $-1$，否则答案为 $idx[i - 1]$

代码实现

class Solution {
public:
    vector<int> occurrencesOfElement(vector<int>& nums, vector<int>& queries, int x) {
        vector<int> idx;
        for(int i = 0; i < nums.size(); ++i) {
            if(nums[i] == x)
                idx.emplace_back(i);
        }
        int m = idx.size();
        vector<int> ans;
        for(int& i : queries) {
            ans.emplace_back(i > m ? -1 : idx[i - 1]);
        }
        return ans;
    }
};

复杂度分析

  • 时间复杂度：$O(n + q)$，其中 $q$ 为 $queries$ 的长度
  • 空间复杂度：$O(n)$