Skip to content

Latest commit

 

History

History
173 lines (132 loc) · 4.9 KB

README_EN.md

File metadata and controls

173 lines (132 loc) · 4.9 KB
Raw
comments difficulty edit_url rating source tags
true
Medium
1262
Biweekly Contest 131 Q2
Array
Hash Table

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.

Python3

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]

Java

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;
    }
}

C++

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;
    }
};

Go

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 i-1 < len(ids) {
			ans = append(ans, ids[i-1])
		} else {
			ans = append(ans, -1)
		}
	}
	return
}

TypeScript

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);
}