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

Leetcode打卡：查询数组中元素出现的位置

article 2024/12/28 23:53:06

执行结果：通过

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

给你一个整数数组 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

`代码以及解题思路`

`代码`

int* occurrencesOfElement(int* nums, int numsSize, int* queries, int queriesSize, int x, int* returnSize) {
    int* indices = (int*)malloc(numsSize * sizeof(int));
    int indicesSize = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == x) {
            indices[indicesSize++] = i;
        }
    }
    int* res = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    for (int i = 0; i < queriesSize; i++) {
        if (indicesSize < queries[i]) {
            res[i] = -1;
        } else {
            res[i] = indices[queries[i] - 1];
        }
    }
    free(indices);
    return res;

}

解题思路：

参数解释:
- int* nums: 指向整数数组的指针，该数组包含一系列整数。
- int numsSize: 数组 nums 的大小（即包含的元素数量）。
- int* queries: 指向查询数组的指针，该数组包含一系列位置索引。
- int queriesSize: 查询数组 queries 的大小（即包含的位置索引数量）。
- int x: 需要查找的元素值。
- int* returnSize: 指向一个整数的指针，用于存储返回结果数组的大小。
步骤解析:
- 步骤1: 分配内存给 indices 数组。这个数组将用于存储元素 x 在 nums 中出现的所有索引位置。分配的内存大小为 numsSize * sizeof(int)，因为 indices 数组的每个元素都是 int 类型。
- 步骤2: 遍历 nums 数组，找到所有等于 x 的元素的索引，并将这些索引存储在 indices 数组中。indicesSize 用于记录当前已经存储的索引数量。
- 步骤3: 分配内存给 res 数组。这个数组将用于存储查询结果。分配的内存大小为 queriesSize * sizeof(int)，因为 res 数组的每个元素都是 int 类型。
- 步骤4: 设置 *returnSize 为 queriesSize，表示返回结果数组的大小与查询数组的大小相同。
- 步骤5: 遍历 queries 数组，对于每个查询位置 queries[i]：
  - 如果 indicesSize（即元素 x 出现的次数）小于 queries[i]，说明查询的位置超出了元素 x 实际出现的次数，因此将 -1 存储在 res[i] 中。
  - 否则，由于 queries 数组中的索引是从 1 开始的（题目可能假设如此，因为直接使用了 queries[i] - 1），需要将查询位置减 1 后从 indices 数组中取出对应的位置索引，存储在 res[i] 中。
- 步骤6: 释放 indices 数组分配的内存，因为它不再需要。
- 步骤7: 返回 res 数组，它包含了所有查询的结果。