Description#
Given an integer array nums containing n integers, find the beauty of each subarray of size k.
The beauty of a subarray is the xth smallest integer in the subarray if it is negative, or 0 if there are fewer than x negative integers.
Return an integer array containing n - k + 1 integers, which denote the beauty of the subarrays in order from the first index in the array.
Example 1:
Input: nums = [1,-1,-3,-2,3], k = 3, x = 2
Output: [-1,-2,-2]
Explanation: There are 3 subarrays with size k = 3.
The first subarray is [1, -1, -3] and the 2nd smallest negative integer is -1.
The second subarray is [-1, -3, -2] and the 2nd smallest negative integer is -2.
The third subarray is [-3, -2, 3] and the 2nd smallest negative integer is -2.
Example 2:
Input: nums = [-1,-2,-3,-4,-5], k = 2, x = 2
Output: [-1,-2,-3,-4]
Explanation: There are 4 subarrays with size k = 2.
For [-1, -2], the 2nd smallest negative integer is -1.
For [-2, -3], the 2nd smallest negative integer is -2.
For [-3, -4], the 2nd smallest negative integer is -3.
For [-4, -5], the 2nd smallest negative integer is -4.
Example 3:
Input: nums = [-3,1,2,-3,0,-3], k = 2, x = 1
Output: [-3,0,-3,-3,-3]
Explanation: There are 5 subarrays with size k = 2.
For [-3, 1], the 1st smallest negative integer is -3.
For [1, 2], there is no negative integer so the beauty is 0.
For [2, -3], the 1st smallest negative integer is -3.
For [-3, 0], the 1st smallest negative integer is -3.
For [0, -3], the 1st smallest negative integer is -3.
Constraints:
n == nums.length 1 <= n <= 1051 <= k <= n1 <= x <= k -50 <= nums[i] <= 50
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
| from sortedcontainers import SortedList
class Solution:
def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:
sl = SortedList(nums[:k])
ans = [sl[x - 1] if sl[x - 1] < 0 else 0]
for i in range(k, len(nums)):
sl.remove(nums[i - k])
sl.add(nums[i])
ans.append(sl[x - 1] if sl[x - 1] < 0 else 0)
return ans
|
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
28
| class Solution {
public int[] getSubarrayBeauty(int[] nums, int k, int x) {
int n = nums.length;
int[] cnt = new int[101];
for (int i = 0; i < k; ++i) {
++cnt[nums[i] + 50];
}
int[] ans = new int[n - k + 1];
ans[0] = f(cnt, x);
for (int i = k, j = 1; i < n; ++i) {
++cnt[nums[i] + 50];
--cnt[nums[i - k] + 50];
ans[j++] = f(cnt, x);
}
return ans;
}
private int f(int[] cnt, int x) {
int s = 0;
for (int i = 0; i < 50; ++i) {
s += cnt[i];
if (s >= x) {
return i - 50;
}
}
return 0;
}
}
|
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
28
| class Solution {
public:
vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
int n = nums.size();
int cnt[101]{};
for (int i = 0; i < k; ++i) {
++cnt[nums[i] + 50];
}
vector<int> ans(n - k + 1);
auto f = [&](int x) {
int s = 0;
for (int i = 0; i < 50; ++i) {
s += cnt[i];
if (s >= x) {
return i - 50;
}
}
return 0;
};
ans[0] = f(x);
for (int i = k, j = 1; i < n; ++i) {
++cnt[nums[i] + 50];
--cnt[nums[i - k] + 50];
ans[j++] = f(x);
}
return ans;
}
};
|
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
| func getSubarrayBeauty(nums []int, k int, x int) []int {
n := len(nums)
cnt := [101]int{}
for _, x := range nums[:k] {
cnt[x+50]++
}
ans := make([]int, n-k+1)
f := func(x int) int {
s := 0
for i := 0; i < 50; i++ {
s += cnt[i]
if s >= x {
return i - 50
}
}
return 0
}
ans[0] = f(x)
for i, j := k, 1; i < n; i, j = i+1, j+1 {
cnt[nums[i]+50]++
cnt[nums[i-k]+50]--
ans[j] = f(x)
}
return ans
}
|
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
| function getSubarrayBeauty(nums: number[], k: number, x: number): number[] {
const n = nums.length;
const cnt: number[] = new Array(101).fill(0);
for (let i = 0; i < k; ++i) {
++cnt[nums[i] + 50];
}
const ans: number[] = new Array(n - k + 1);
const f = (x: number): number => {
let s = 0;
for (let i = 0; i < 50; ++i) {
s += cnt[i];
if (s >= x) {
return i - 50;
}
}
return 0;
};
ans[0] = f(x);
for (let i = k, j = 1; i < n; ++i, ++j) {
cnt[nums[i] + 50]++;
cnt[nums[i - k] + 50]--;
ans[j] = f(x);
}
return ans;
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution:
def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:
def f(x: int) -> int:
s = 0
for i in range(50):
s += cnt[i]
if s >= x:
return i - 50
return 0
cnt = [0] * 101
for v in nums[:k]:
cnt[v + 50] += 1
ans = [f(x)]
for i in range(k, len(nums)):
cnt[nums[i] + 50] += 1
cnt[nums[i - k] + 50] -= 1
ans.append(f(x))
return ans
|
