Skip to content

Latest commit

 

History

History
175 lines (132 loc) · 4.83 KB

README.md

File metadata and controls

175 lines (132 loc) · 4.83 KB
Raw
comments difficulty edit_url rating source tags
true
中等
1262
第 131 场双周赛 Q2
数组
哈希表

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

English Version

题目描述

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

解法

方法一：模拟

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

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

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

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