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

LeetCode 滑动窗口滑动子数组的美丽值

article 2024/9/20 15:35:24

滑动子数组的美丽值

给你一个长度为 n 的整数数组 nums ，请你求出每个长度为 k 的子数组的美丽值。
一个子数组的美丽值定义为：如果子数组中第 x 小整数是负数，那么美丽值为第 x 小的数，否则美丽值为 0 。
请你返回一个包含 n - k + 1 个整数的数组，依次表示数组中从第一个下标开始，每个长度为 k 的子数组的美丽值。
子数组指的是数组中一段连续非空的元素序列。
示例 1：
输入：nums = [1,-1,-3,-2,3], k = 3, x = 2
输出：[-1,-2,-2]
解释：总共有 3 个 k = 3 的子数组。
第一个子数组是 [1, -1, -3] ，第二小的数是负数 -1 。
第二个子数组是 [-1, -3, -2] ，第二小的数是负数 -2 。
第三个子数组是 [-3, -2, 3] ，第二小的数是负数 -2 。
示例 2：
输入：nums = [-1,-2,-3,-4,-5], k = 2, x = 2
输出：[-1,-2,-3,-4]
解释：总共有 4 个 k = 2 的子数组。
[-1, -2] 中第二小的数是负数 -1 。
[-2, -3] 中第二小的数是负数 -2 。
[-3, -4] 中第二小的数是负数 -3 。
[-4, -5] 中第二小的数是负数 -4 。
示例 3：
输入：nums = [-3,1,2,-3,0,-3], k = 2, x = 1
输出：[-3,0,-3,-3,-3]
解释：总共有 5 个 k = 2 的子数组。
[-3, 1] 中最小的数是负数 -3 。
[1, 2] 中最小的数不是负数，所以美丽值为 0 。
[2, -3] 中最小的数是负数 -3 。
[-3, 0] 中最小的数是负数 -3 。
[0, -3] 中最小的数是负数 -3 。
提示：
n == nums.length
1 <= n <= 105
1 <= k <= n
1 <= x <= k
-50 <= nums[i] <= 50

解题思路

滑动数组 + 暴力枚举

题目是要求计算定长子数组的美丽值，所以采用定长滑动窗口进行枚举

接下来是计算美丽值，也就是找到子数组的第X小的数

由于-50 <= nums[i] <= 50 也就是数组的值范围比较小，所以可以采用一个数组 arr 记录各个数字出现的次数，然后遍历这个数组，找到第X小的数，暴力枚举出美丽值

关于如何找到第X小的数：我们用数组记录各个数字出现的次数时，由于数组的小标大于等于0，所以我们要对数字+50，那么数组的下标-50就是对应的数字。因为第X小的数若是非负数，美丽值则为0，所以只需要计算负数的出现次数，暴力枚举只需要枚举到数组的49下标。在暴力枚举中，我们统计出现的数字的个数 sum，也就是对 arr 的数据进行累加，当 sum 首次大于等于 x 时，此时的下标-50就是第X小的数，也就是美丽值，然后退出循环。若循环正常结束，则美丽值为0。

代码如下↓

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* getSubarrayBeauty(int* nums, int numsSize, int k, int x, int* returnSize){
    int compare(int* a,int* b)
    {
        return *a - *b;
    }
    int f=-1;
    int* res = (int*)malloc(sizeof(int)*(numsSize-k+1));
    int arr[101];
    memset(arr,0,sizeof(arr));
    int l=0,r=k-1;
    *returnSize = numsSize-k+1;
    for(int i=0;i<k;i++)
    {
        arr[nums[i]+50]++;
    }
    int sum=0;
    int ff=1;
    for(int i=0;i<50;i++)
    {
        sum+=arr[i];
        if(sum>=x)
        {
            res[++f] = i-50;
            ff=0;
            break;
        }
    }
    if(ff)
    {
        res[++f] = 0;
    }
    while(r<numsSize-1)
    {
        arr[nums[l]+50]--;
        l++;
        r++;
        arr[nums[r]+50]++;
        sum=0;
        ff=1;
        for(int i=0;i<50;i++)
        {
            sum+=arr[i];
            if(sum>=x)
            {
                res[++f] = i-50;
                ff=0;
                break;
            }
        }
        if(ff)
        {
            res[++f] = 0;
        }
    }
    return res;
}