LeetCode 3159.查询数组中元素的出现位置：存x下标

【LetMeFly】3159.查询数组中元素的出现位置：存x下标

力扣题目链接：https://leetcode.cn/problems/find-occurrences-of-an-element-in-an-array/

给你一个整数数组 nums ，一个整数数组 queries 和一个整数 x 。

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

请你返回一个整数数组 answer ，包含所有查询的答案。

 

示例 1：

输出：[0,-1,2,-1]

解释：

• 第 1 个查询，第一个 1 出现在下标 0 处。
• 第 2 个查询，nums 中只有两个 1 ，所以答案为 -1 。
• 第 3 个查询，第二个 1 出现在下标 2 处。
• 第 4 个查询，nums 中只有两个 1 ，所以答案为 -1 。

示例 2：

输出：[-1]

解释：

• 第 1 个查询，nums 中没有 5 ，所以答案为 -1 。

 

提示：

• 1 <= nums.length, queries.length <= 105
• 1 <= queries[i] <= 105
• 1 <= nums[i], x <= 104

解题方法：模拟

首先遍历一遍nums数组，将x的下标存到locs数组中。

接着遍历queries数组，对于其中的一个query，如果query > len(locs)则查询结果为-1，否则查询结果为locs[query - 1]。

• 时间复杂度$O(len(nums)+len(queries))$
• 空间复杂度$O(len(nums))$

AC代码

C++

/** @Author: LetMeFly* @Date: 2024-12-27 12:13:46* @LastEditors: LetMeFly.xyz* @LastEditTime: 2024-12-27 12:14:52*/
class Solution {
public:vector<int> occurrencesOfElement(vector<int>& nums, vector<int>& queries, int x) {vector<int> locs;for (int i = 0; i < nums.size(); i++) {if (nums[i] == x) {locs.push_back(i);}}vector<int> ans(queries.size());for (int i = 0; i < queries.size(); i++) {ans[i] = queries[i] > locs.size() ? -1 : locs[queries[i] - 1];}return ans;}
};

Python

'''
Author: LetMeFly
Date: 2024-12-27 12:16:30
LastEditors: LetMeFly.xyz
LastEditTime: 2024-12-27 12:18:08
'''
from typing import Listclass Solution:def occurrencesOfElement(self, nums: List[int], queries: List[int], x: int) -> List[int]:locs = [i for i in range(len(nums)) if nums[i] == x]return [-1 if q > len(locs) else locs[q - 1] for q in queries]

Java

/** @Author: LetMeFly* @Date: 2024-12-27 12:18:32* @LastEditors: LetMeFly.xyz* @LastEditTime: 2024-12-27 12:20:43*/
import java.util.ArrayList;class Solution {public int[] occurrencesOfElement(int[] nums, int[] queries, int x) {ArrayList<Integer> locs = new ArrayList<>();for (int i = 0; i < nums.length; i++) {if (nums[i] == x) {locs.add(i);}}int[] ans = new int[queries.length];for (int i = 0; i < queries.length; i++) {if (queries[i] > locs.size()) {ans[i] = -1;} else {ans[i] = locs.get(queries[i] - 1);}}return ans;}
}

Go

/** @Author: LetMeFly* @Date: 2024-12-27 12:22:32* @LastEditors: LetMeFly.xyz* @LastEditTime: 2024-12-27 12:23:51*/
package mainfunc occurrencesOfElement(nums []int, queries []int, x int) []int {locs := make([]int, 0)for i, v := range nums {if v == x {locs = append(locs, i)}}ans := make([]int, 0)for _, q := range queries {if q > len(locs) {ans = append(ans, -1)} else {ans = append(ans, locs[q - 1])}}return ans
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/144765228