flask做的网站有哪些,全国分类信息网站排名,建设部职业资格注册中心网站,丰台专业网站建设公司Problem: 2653. 滑动子数组的美丽值 滑动子数组的美丽值
问题描述
给定一个长度为 n 的整数数组 nums#xff0c;我们需要计算每个长度为 k 的子数组的美丽值。
美丽值的定义如下#xff1a;如果子数组中第 x 小的整数是负数#xff0c;那么美丽值为第 x 小的数#xff… Problem: 2653. 滑动子数组的美丽值 滑动子数组的美丽值
问题描述
给定一个长度为 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。
解题思路
这个问题可以使用滑动窗口来解决关键在于如何高效地查询第 x 个小的负数。
我们可以使用一个数组 cnt 来记录每个数出现的次数数组的索引表示数值数组的值表示该数值出现的次数。为了方便我们将数组 cnt 的索引偏移了 50使得所有数值都在 [0, 100] 的范围内。
具体的算法步骤如下
初始化一个长度为 n - k 1 的数组 ans用于存放每个子数组的美丽值。用一个循环遍历数组 nums从 0 到 n-1。 在循环中首先更新 cnt 数组将当前元素的次数加一。然后初始化一个变量 left 为 x表示我们需要找到第 x 小的负数。接下来遍历数组 cnt 中的每一个元素从 0 到 BIAS-1。 对于每个元素将 left 减去该元素的次数。如果 left 小于等于 0说明已经找到了第 x 小的负数将当前元素作为答案并退出循环。 最后更新 cnt 数组将当前子数组的第一个元素的次数减一。 返回数组 ans其中存放着每个子数组的美丽值。
C代码实现
class Solution {
public:vectorint getSubarrayBeauty(vectorint nums, int k, int x) {const int BIAS 50;int cnt[BIAS * 2 1]{0}; // 初始化数组所有元素为0int n nums.size();for (int i 0; i k - 1; i) {cnt[nums[i] BIAS]; // 更新前k-1个元素的次数}vectorint ans(n - k 1); // 初始化答案数组for (int i k - 1; i n; i) {cnt[nums[i] BIAS]; // 更新当前元素的次数int left x; // 初始化left为x// 寻找第x小的负数for (int j 0; j BIAS; j) {left - cnt[j];if (left 0) {ans[i - k 1] j - BIAS; // 找到答案break;}}--cnt[nums[i - k 1] BIAS]; // 更新当前子数组的第一个元素的次数}return ans;}
};
