Welcome to Subscribe On Youtube
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 1^{st} query, the first occurrence of 1 is at index 0.
 For the 2^{nd} query, there are only two occurrences of 1 in
nums
, so the answer is 1.  For the 3^{rd} query, the second occurrence of 1 is at index 2.
 For the 4^{th} 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 1^{st} query, 5 doesn't exist in
nums
, so the answer is 1.
Constraints:
1 <= nums.length, queries.length <= 10^{5}
1 <= queries[i] <= 10^{5}
1 <= nums[i], x <= 10^{4}
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.

class Solution { public int[] occurrencesOfElement(int[] nums, int[] queries, int x) { List<Integer> ids = new ArrayList<>(); for (int i = 0; i < nums.length; ++i) { if (nums[i] == x) { ids.add(i); } } int m = queries.length; int[] ans = new int[m]; for (int i = 0; i < m; ++i) { int j = queries[i]  1; ans[i] = j < ids.size() ? ids.get(j) : 1; } return ans; } }

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

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]

func occurrencesOfElement(nums []int, queries []int, x int) (ans []int) { ids := []int{} for i, v := range nums { if v == x { ids = append(ids, i) } } for _, i := range queries { if i1 < len(ids) { ans = append(ans, ids[i1]) } else { ans = append(ans, 1) } } return }

function occurrencesOfElement(nums: number[], queries: number[], x: number): number[] { const ids: number[] = nums.map((v, i) => (v === x ? i : 1)).filter(v => v !== 1); return queries.map(i => ids[i  1] ?? 1); }