3159. Find Occurrences of an Element in an Array
Description
You are given an integer array nums
, an integer array queries
, and an integer x
.
For each queries[i]
, you need to find the index of the queries[i]th
occurrence of x
in the nums
array. If there are fewer than queries[i]
occurrences of x
, the answer should be -1 for that query.
Return an integer array answer
containing the answers to all queries.
Example 1:
Input: nums = [1,3,1,7], queries = [1,3,2,4], x = 1
Output: [0,-1,2,-1]
Explanation:
- For the 1st query, the first occurrence of 1 is at index 0.
- For the 2nd query, there are only two occurrences of 1 in
nums
, so the answer is -1. - For the 3rd query, the second occurrence of 1 is at index 2.
- For the 4th query, there are only two occurrences of 1 in
nums
, so the answer is -1.
Example 2:
Input: nums = [1,2,3], queries = [10], x = 5
Output: [-1]
Explanation:
- For the 1st query, 5 doesn't exist in
nums
, so the answer is -1.
Constraints:
1 <= nums.length, queries.length <= 105
1 <= queries[i] <= 105
1 <= nums[i], x <= 104
Solutions
Solution 1: Simulation
According to the problem description, we can first traverse the array nums
to find the indices of all elements with a value of $x$, and record them in the array ids
.
Next, we traverse the array queries
. For each query $i$, if $i - 1$ is less than the length of ids
, then the answer is ids[i - 1]
, otherwise, the answer is $-1$.
The time complexity is $O(n + m)$, and the space complexity is $O(n + m)$. Where $n$ and $m$ are the lengths of the arrays nums
and queries
respectively.
1 2 3 4 5 6 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 |
|