2024-12-29：查询数组中元素的出现位置。用go语言，给定一个整数数组 nums、一个整数数组 queries 和一个整数 x。

对于每个查询 queries[i]，你需要在 nums 中找到第 queries[i] 次出现的 x 的位置。

如果 x 在 nums 中的出现次数少于 queries[i]，则该查询的结果应为 -1。

请返回一个包含所有查询结果的整数数组 answer。

1 <= nums.length, queries.length <= 100000。

1 <= queries[i] <= 100000。

1 <= nums[i], x <= 10000。

输入：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 。

答案2024-12-29：

chatgpt[1]

题目来自leetcode3158。

大体步骤如下：

1.定义一个函数 occurrencesOfElement，接收三个参数 nums []int, queries []int, x int，用来查询数组中元素的出现位置。

2.在函数内部，初始化两个空slice indices 和 res 来分别存储元素 x 在 nums 中的索引位置和查询结果。

3.遍历 nums 切片，找出所有元素 x 的索引位置，并存储在 indices 中。

4.遍历 queries 切片，在 res 中添加对应查询的结果：

• ? 如果 indices 的长度小于当前查询值 q（queries[i])，说明查询的次数超过了 x 在 nums 中出现的次数，将 -1 添加到 res 中。
• ? 否则，将 x 在 nums 中第 q 次出现的索引（通过 indices[q-1]）添加到 res 中。

5.返回结果 res。

6.在 main 函数中，定义输入数组 nums := []int{1,3,1,7}，查询数组 queries := []int{1,3,2,4}，以及元素 x 的值 x := 1。

7.调用 occurrencesOfElement 函数，并将结果打印输出。

总的时间复杂度：

• ? 遍历 nums 找出元素 x 的索引位置需要 O(N) 的时间复杂度，其中 N 为 nums 切片的长度。
• ? 遍历 queries，并根据查询结果进行操作，需要花费 O(M) 的时间复杂度，其中 M 为 queries 切片的长度。

总的额外空间复杂度：

• ? indices 和 res 两个额外的切片，对应 O(N) 的空间复杂度，其中 N 为 nums 切片的长度。
• ? 常量级别的变量占用空间可以忽略不计。

综合来看，该程序的时间复杂度为 O(N+M)，空间复杂度为 O(N)。

Go完整代码如下：

package main

import "fmt"

func occurrencesOfElement(nums []int, queries []int, x int) []int {
    indices := []int{}
    for i, num := range nums {
        if num == x {
            indices = append(indices, i)
        }
    }
    res := []int{}
    for _, q := range queries {
        if len(indices) < q {
            res = append(res, -1)
        } else {
            res = append(res, indices[q-1])
        }
    }
    return res
}

func main() {
    nums := []int{1,3,1,7}
    queries := []int{1,3,2,4}
    x := 1
    result := occurrencesOfElement(nums,queries,x)
    fmt.Println(result) 
}

Rust完整代码如下：

fn occurrences_of_element(nums: &[i32], queries: &[usize], x: i32) -> Vec {
    let mut indices = Vec::new();
    
    // 找出 x 在 nums 中的所有索引
    for (i, &num) in nums.iter().enumerate() {
        if num == x {
            indices.push(i);
        }
    }
    
    let mut res = Vec::new();
    
    // 根据 queries 中的索引返回结果
    for &q in queries {
        if q == 0 || q > indices.len() {
            res.push(-1);
        } else {
            res.push(indices[q - 1] as i32);
        }
    }
    
    res
}

fn main() {
    let nums = vec![1, 3, 1, 7];
    let queries = vec![1, 3, 2, 4];
    let x = 1;
    
    let result = occurrences_of_element(&nums, &queries, x);
    println!("{:?}", result); 
}

引用链接

[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP