class Solution {
public:
vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
}
};
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 。
提示：
n == nums.length 1 <= n <= 1051 <= k <= n1 <= x <= k -50 <= nums[i] <= 50 原站题解
golang 解法, 执行用时: 336 ms, 内存消耗: 9.5 MB, 提交时间: 2023-05-05 17:06:35
func getSubarrayBeauty(nums []int, k, x int) []int {
const bias = 50
cnt := [bias*2 + 1]int{}
for _, num := range nums[:k-1] { // 先往窗口内添加 k-1 个数
cnt[num+bias]++
}
ans := make([]int, len(nums)-k+1)
for i, num := range nums[k-1:] {
cnt[num+bias]++ // 进入窗口（保证窗口有恰好 k 个数）
left := x
for j, c := range cnt[:bias] { // 暴力枚举负数范围 [-50,-1]
left -= c
if left <= 0 { // 找到美丽值
ans[i] = j - bias
break
}
}
cnt[nums[i]+bias]-- // 离开窗口
}
return ans
}
java 解法, 执行用时: 33 ms, 内存消耗: 59 MB, 提交时间: 2023-05-05 17:06:23
class Solution {
public int[] getSubarrayBeauty(int[] nums, int k, int x) {
final int BIAS = 50;
var cnt = new int[BIAS * 2 + 1];
int n = nums.length;
for (int i = 0; i < k - 1; ++i) // 先往窗口内添加 k-1 个数
++cnt[nums[i] + BIAS];
var ans = new int[n - k + 1];
for (int i = k - 1; i < n; ++i) {
++cnt[nums[i] + BIAS]; // 进入窗口（保证窗口有恰好 k 个数）
int left = x;
for (int j = 0; j < BIAS; ++j) { // 暴力枚举负数范围 [-50,-1]
left -= cnt[j];
if (left <= 0) { // 找到美丽值
ans[i - k + 1] = j - BIAS;
break;
}
}
--cnt[nums[i - k + 1] + BIAS]; // 离开窗口
}
return ans;
}
}
python3 解法, 执行用时: 2564 ms, 内存消耗: 28.2 MB, 提交时间: 2023-05-05 17:06:09
'''
滑动窗口。
由于值域很小,所以借鉴计数排序,用一个cnt数组维护窗口内每个数的出现次数。然后遍历cnt去求第x小的数。
什么是第x小的数? 设它是num,那么小于num的数有小于x个,就说明 num是第x小的数。
'''
class Solution:
def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:
cnt = [0] * 101
for num in nums[:k - 1]: # 先往窗口内添加 k-1 个数
cnt[num] += 1
ans = [0] * (len(nums) - k + 1)
for i, (in_, out) in enumerate(zip(nums[k - 1:], nums)):
cnt[in_] += 1 # 进入窗口（保证窗口有恰好 k 个数）
left = x
for j in range(-50, 0): # 暴力枚举负数范围 [-50,-1]
left -= cnt[j]
if left <= 0: # 找到美丽值
ans[i] = j
break
cnt[out] -= 1 # 离开窗口
return ans