给你一个长度为 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
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sliding-subarray-beauty
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
周赛第三题。前两题简单题。结果第三题被打回原形，再次成为一名光荣的两题选手。。。
初步思路是滑动窗口加二分查找。
即维护前 k 个数的排序。
时间复杂度应该是 O(n * k * log(k))，n 是数组长度，k 是需要维护的数组长度，log(k)是二分查找所需时间。
最后几个测试用例超时了。
改换思路。
由于数据范围是 -50 到 50 之间。因此可以用计数排序。
代码如下：
二分查找：
class Solution {
public int[] getSubarrayBeauty (int[] nums, int k, int x) {
int[] arr = new int[k];
System.arraycopy(nums, 0, arr, 0, k);
Arrays.sort(arr);
int[] res = new int[nums.length - k + 1];
res[0] = Math.min(arr[x - 1], 0);
for (int i = k; i < nums.length; i++) {
sort(arr, nums[i - k], nums[i]);
res[i - k + 1] = Math.min(arr[x - 1], 0);
}
return res;
}
// 搜索某个元素在数组中的位置。
private int search (int[] arr, int num) {
int len = arr.length;
if (arr[0] > num) {
return -1;
} else if (arr[len - 1] < num) {
return len;
}
int left = 0;
int right = len - 1;
while (left < right) {
int tem = (left + right) / 2;
if (arr[tem] < num) {
left = tem + 1;
} else if (arr[tem] > num) {
right = tem - 1;
} else {
return tem;
}
}
return left;
}
// 对数组进行删除 num1，添加 num2 的维护。
private void sort (int[] arr, int num1, int num2) {
int index1 = search(arr, num1);
int index2 = search(arr, num2);
if (index2 <= -1) {
for (int i = index1; i > 0; i --) {
arr[i] = arr[i - 1];
}
arr[0] = num2;
} else if (index2 >= arr.length) {
for (int i = index1; i < arr.length - 1; i ++) {
arr[i] = arr[i + 1];
}
arr[arr.length - 1] = num2;
} else {
if (arr[index2] <= num2) {
if (index2 > index1) {
for (int i = index1; i < index2; i ++) {
arr[i] = arr[i + 1];
}
arr[index2] = num2;
} else if (index2 < index1) {
for (int i = index1; i > index2 + 1; i --) {
arr[i] = arr[i - 1];
}
arr[index2 + 1] = num2;
} else {
arr[index1] = num2;
}
} else {
if (index2 > index1) {
for (int i = index1; i < index2 - 1; i++) {
arr[i] = arr[i + 1];
}
arr[index2 - 1] = num2;
} else if (index2 < index1) {
for (int i = index1; i >index2; i --) {
arr[i] = arr[i - 1];
}
arr[index2] = num2;
} else {
arr[index1] = num2;
}
}
}
}
}
计数排序：
class Solution {
public int[] getSubarrayBeauty (int[] nums, int k, int x) {
int[] arr = new int[101];
for (int i = 0; i < k; i ++) {
arr[nums[i] + 50] ++;
}
int[] res = new int[nums.length - k + 1];
res[0] = Math.min(0, search(arr, x));
for (int i = k; i < nums.length; i ++) {
upDate(arr, nums[i - k], nums[i]);
res[i - k + 1] = Math.min(0, search(arr, x));
}
return res;
}
private void upDate(int[] arr, int num1, int num2) {
arr[num1 + 50] --;
arr[num2 + 50] ++;
}
private int search(int[] arr, int x) {
int count = 0;
for (int i = 0; i < arr.length; i ++) {
count += arr[i];
if (count >= x) {
return i - 50;
}
}
return -1;
}
}
标签：力扣,arr,num2,nums,2653,---,int,数组,index2 From： https://www.cnblogs.com/allWu/p/17353498.html