What is the most efficient way to find the k-th occurrence of x in nums?

Use a hash map to store all indices of x during a single scan of nums, then answer each query in O(1) time.

What happens if queries[i] is larger than the number of occurrences of x?

Return -1 for that query because the requested occurrence does not exist in nums.

Can this problem be solved without a hash map?

Yes, but scanning nums for each query leads to O(n*q) time which is inefficient for large arrays.

How do I handle multiple queries efficiently?

Precompute a list of all positions where x appears, then access each queries[i]-1 index directly.

Why is this problem categorized under Array scanning plus hash lookup?

Because the optimal solution combines scanning nums once to build a hash map with lists of indices for quick query resolution.

#3159

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

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

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

数组哈希表

题目描述

给你一个整数数组 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⁵
1 <= queries[i] <= 10⁵
1 <= nums[i], x <= 10⁴

lightbulb

解题思路

方法一：模拟

根据题目描述，我们可以先遍历一遍数组 $\textit{nums}$ ，找出所有值为 $x$ 的元素的下标，记录在数组 $\textit{ids}$ 中。

接着遍历数组 $\textit{queries}$ ，对于每个查询 $i$ ，如果 $i - 1$ 小于 $\textit{ids}$ 的长度，那么答案就是 $\textit{ids}[i - 1]$ ，否则答案就是 $-1$ 。

时间复杂度 $O(n + m)$ ，空间复杂度 $O(n + m)$ 。其中 $n$ 和 $m$ 分别是数组 $\textit{nums}$ 和数组 $\textit{queries}$ 的长度。

1

2

3

4

5

6

7

class Solution:
    def occurrencesOfElement(
        self, nums: List[int], queries: List[int], x: int
    ) -> List[int]:
        ids = [i for i, v in enumerate(nums) if v == x]
        return [ids[i - 1] if i - 1 < len(ids) else -1 for i in queries]

speed

复杂度分析

指标	值
时间	complexity is O(n + q) where n is nums length and q is queries length, because nums is scanned once and each query is answered in O(1). Space complexity is O(n) in the worst case for storing all occurrence indices of x.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if candidates precompute occurrence indices or scan nums repeatedly.
question_mark
Listen for hash map usage versus naive iteration for multiple queries.
question_mark
Notice if candidates handle edge cases when occurrences are fewer than query values.

warning

常见陷阱

外企场景

error
Repeatedly scanning nums for each query causing TLE on large inputs.
error
Not handling zero-based indexing properly for queries[i]th occurrence.
error
Assuming every query is valid without checking if x occurs enough times.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count the number of occurrences instead of returning the index.
arrow_right_alt
Return all indices for multiple target values in a single query array.
arrow_right_alt
Find last k occurrences of x instead of the first k occurrences.

help

常见问题

外企场景

继续练习

#3158 求出出现两次数字的 XOR 值 #3160 所有球里面不同颜色的数目 #3162 优质数对的总数 I