网站建设制度制定,wordpress主题哥,东莞做门户网站,旅游网站建设网站滑动子数组的美丽值 给你一个长度为 n 的整数数组 nums #xff0c;请你求出每个长度为 k 的子数组的 美丽值 。 一个子数组的 美丽值 定义为#xff1a;如果子数组中第 x 小整数 是 负数 #xff0c;那么美丽值为第 x 小的数#xff0c;否则美丽值为 0 。 请你返回一个包含…滑动子数组的美丽值 给你一个长度为 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-k1));int arr[101];memset(arr,0,sizeof(arr));int l0,rk-1;*returnSize numsSize-k1;for(int i0;ik;i){arr[nums[i]50];}int sum0;int ff1;for(int i0;i50;i){sumarr[i];if(sumx){res[f] i-50;ff0;break;}}if(ff){res[f] 0;}while(rnumsSize-1){arr[nums[l]50]--;l;r;arr[nums[r]50];sum0;ff1;for(int i0;i50;i){sumarr[i];if(sumx){res[f] i-50;ff0;break;}}if(ff){res[f] 0;}}return res;
}
