题目
给你一个长度为 n 的整数数组 nums ，请你求出每个长度为 k 的子数组的 美丽值 。
一个子数组的 美丽值 定义为：如果子数组中第 x 小整数 是 负数 ，那么美丽值为第 x 小的数，否则美丽值为 0 。
请你返回一个包含 n - k + 1 个整数的数组，依次 表示数组中从第一个下标开始，每个长度为 k 的子数组的 美丽值 。
示例 1：
1
2
3
4
5
6
| 输入：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：
1
2
3
4
5
6
7
| 输入：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：
1
2
3
4
5
6
7
8
| 输入：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
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int[] getSubarrayBeauty(int[] nums, int k, int x) {
int n=nums.length;
int[] bn = new int[n-k+1];
int[] count = new int[50*2+1];
for(int i=0;i<k-1;i++){
count[nums[i]+50]++;
}
int x1;
for(int i=k-1;i<n;i++){
count[nums[i]+50]++;
x1=x;
for(int j=0;j<50;j++){
x1-=count[j];
if(x1<=0){
bn[i-(k-1)]=j-50;
break;
}
}
count[nums[i-(k-1)]+50]--;
}
return bn;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class Solution {
public int[] getSubarrayBeauty(int[] nums, int k, int x) {
int n=nums.length;
int[] temp = new int[k];
int[] b = new int[n-k+1];
List<Integer> list = new ArrayList<>();
int count=0;
for(int i=0;i<n;i++){
list.add(nums[i]);
if(i<k-1){
continue;
}
temp = list.stream().mapToInt(Integer::intValue).toArray();
Arrays.sort(temp);
if(temp[x-1]<0){
b[count]=temp[x-1];
}else{
b[count]=0;
}
count++;
list.remove(Integer.valueOf(nums[i-(k-1)]));
}
return b;
}
}
|
知识点
滑动窗口 + 计数排序。
思路：在于如何理解第x小的数。
假设第x小的数为num，那么小于num的数的个数肯定小于x，大于num的数的个数肯定大于等于x。两个条件结合才能保证num为第x小的数。
