力扣2653.滑动子数组的美丽值

力扣2653.滑动子数组的美丽值

• 计数排序：数值作为下标 记录个数

  • 求第x小的数 ： 暴力枚举负数 直到找到第x个负数

•   class Solution {
    public:
        vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
            const int BIAS = 50;
            int cnt[BIAS * 2 + 1],n = nums.size();
            for(int i=0;i<k-1;i++)
                cnt[nums[i]+BIAS] ++;  //记录数组值
            vector<int> ans(n-k+1);
            for(int i=k-1;i<n;i++)
            {
                cnt[nums[i] + BIAS] ++ ;
                int left = x;
                for(int j=0;j<BIAS;j++)  //暴力枚举所有负数
                {
                    left -= cnt[j];
                    if(left <= 0)  //说明一共找到了x个负数
                    {
                        ans[i-k+1] = j - BIAS;
                        break;
                    }
                }
                cnt[nums[i-k+1] + BIAS] --;
            }
            return ans;
        }
    };