当前位置：首页 > article >正文

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

article 2025/3/1 10:46:29

【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：

输入：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 <= 10⁵
1 <= queries[i] <= 10⁵
1 <= nums[i], x <= 10⁴

解题方法：模拟

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

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

时间复杂度 $O (l e n (n u m s) + l e n (q u er i es))$
空间复杂度 $O (l e n (n u m s))$

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 List

class 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 main

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