用kotlin解决这个题目:2653. 滑动子数组的美丽值 提示 中等 26 相关企业 给你一个长度为 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
时间: 2023-11-27 16:50:58 浏览: 71
```kotlin
fun beautySum(nums: IntArray, k: Int, x: Int): IntArray {
val n = nums.size
val res = IntArray(n - k + 1)
val negCount = IntArray(101)
var negNum = 0
for (i in 0 until k) {
if (nums[i] < 0) {
negCount[-nums[i]]++
negNum++
}
}
for (i in 0 until n - k + 1) {
if (i > 0) {
if (nums[i - 1] < 0) {
negCount[-nums[i - 1]]--
if (negCount[x] > negNum - negCount[x]) {
res[i - 1] = x
} else if (negCount[x] == negNum - negCount[x]) {
res[i - 1] = -x
}
negNum--
}
if (nums[i + k - 1] < 0) {
negCount[-nums[i + k - 1]]++
negNum++
}
}
if (negCount[x] > negNum - negCount[x]) {
res[i] = x
} else if (negCount[x] == negNum - negCount[x]) {
res[i] = -x
}
}
return res
}
```
解题思路:
- 维护一个长度为 k 的滑动窗口,用桶记录窗口内每个数的出现次数。
- 维护一个变量 negNum 记录窗口内负数的数量。
- 对于每个长度为 k 的子数组,查询第 x 小的负数,判断它的数量是否超过一半,确定其美丽值。如果数量相等,则美丽值为 0。
时间复杂度:O(n + 100k),其中 n 是数组长度,100k 是桶的大小,因为所有数的范围是 [-50, 50],所以桶的大小是 101。
阅读全文