力扣 2

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

力扣正在保持打卡，目前在用C语言，等到寒假再正式转到Java

审题

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

原始题目：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* occurrencesOfElement(int* nums, int numsSize, int* queries, int queriesSize, int x, int* returnSize) {
    
}

思路

最开始的思路比较直接，你问我第queries[i]个x的位置，那我就遍历queriesSize次queries数组，每次都去遍历一遍nums数组，然后再比较，代码如下

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* occurrencesOfElement(int* nums, int numsSize, int* queries, int queriesSize, int x, int* returnSize) {
    static int arr[100000]={};
    for(int i = 0;i < queriesSize; i++){
        int j = 0;
        int temp = queries[i];
        while(1){
            int flag = 0;
            for(j = 0;j<numsSize;j++){
                if(nums[j] == x && temp !=0)
                {
                    temp -= 1;
                }
                if (temp == 0) break;
            }
            if(temp == 0){
                arr[i] = j;
                break;
            }else if(temp != 0){
                arr[i] = -1;
                break;
            }
        }
    }
    *returnSize = queriesSize;
    return arr;
}

其中要注意的是

if(nums[j] == x && temp !=0)
{
    temp -= 1;
}
if (temp == 0) break;

这里的条件，temp是辅助计数的，如果temp等于0，就不要再减了，直接break，整体想法比较简单。运行一下！

爽了，点击提交！

额，看来循环嵌套时间复杂度太大了，面对超大数组应付不过来，换个思路。

我们其实可以在程序一开始就对数组进行针对x的遍历，同时计数有多少个x，同时记录x的下标，再去对queries遍历，如果queries[i]大于count，那就意味着数组中没有满足条件的元素，返回-1，反之如果小于等于，则说明存在，返回下标数组[queries[i] - 1]（-1是因为下标从0开始）即可。

遍历部分：

//这里的temp就是存储下标的数组，count不仅可以计数，也可以用来做数组的下标
    int count = 0;
    for(int i = 0;i < numsSize;i++){
        if(nums[i] == x){
            temp[count++] = i;
        }
    }


//判断queries[j]与count的大小关系，分别向answer数组中填入对应下标值或者-1;    
    for(int j = 0;j < queriesSize;j++){
        if(count >= queries[j]) answer[j] = temp[queries[j] - 1];
        else answer[j] = -1;
    }

同时，代码使用了动态数组 int* temp = (int*)malloc(numsSize * sizeof(int));
语法比较简单，可以加上free(temp)释放内存

到此结束

代码

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* occurrencesOfElement(int* nums, int numsSize, int* queries, int queriesSize, int x, int* returnSize) {
    int* temp = (int*)malloc(numsSize * sizeof(int));
    int count = 0;
    for(int i = 0;i < numsSize;i++){
        if(nums[i] == x){
            temp[count++] = i;
        }
    }
    int* answer = (int*)malloc(queriesSize * sizeof(int));
    for(int j = 0;j < queriesSize;j++){
        if(count >= queries[j]) answer[j] = temp[queries[j] - 1];
        else answer[j] = -1;
    }
    *returnSize = queriesSize;
    return answer; 
}