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.
- A subarray is a contiguous non-empty sequence of elements within an 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.length1 <= n <= 1051 <= k <= n1 <= x <= k-50 <= nums[i] <= 50
Solution: Sliding Window + Counter
Since the range of nums are very small (-50 ~ 50), we can use a counter to track the frequency of each element, s.t. we can find the k-the smallest element in O(50) instead of O(k).
Time complexity: O((n – k + 1) * 50)
Space complexity: O(50)
C++
|
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 |
// Author: Huahua class Solution { public: vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) { constexpr int kMax = 50; const int n = nums.size(); vector<int> counts(2 * kMax + 1); vector<int> ans; for (int i = 0; i < n; ++i) { if (i >= k) --counts[nums[i - k] + kMax]; ++counts[nums[i] + kMax]; if (i >= k - 1) { int b = 0; for (int j = 0, s = 0; j <= kMax; ++j) { s += counts[j]; if (s >= x) { b = j - kMax; break; } } ans.push_back(b); } } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment