- 難度分: 1786
- 我覺得這一題稍有難度，主要在處理
findKth 方法時，有一些技巧，如果單純用 vector 來記錄 window，會 LTE，因為 nums[i] 的範圍滿小的(-50~50之間)，可以用 bucket sort，如果數字再更大一點，可以使用 fenwick tree 或是 segment tree 範圍求和，使 update 與 query 的複雜度都是 log(n) - Bucket Sort
class NumberTracker {
public:
virtual void update(int num, int delta) = 0;
virtual int findKth(int k) = 0;
virtual ~NumberTracker() {}
};
class BucketSort : public NumberTracker {
private:
vector<int> cnt;
int left_;
int right_;
int n_;
public:
BucketSort(int left, int right) {
left_ = left;
right_ = right;
n_ = right - left + 1;
cnt.assign(n_, 0);
}
void update(int num, int delta) override {
cnt[num - left_] += delta;
}
int findKth(int k) override {
int total = 0;
for (int i = 0; i <= n_; i++) {
total += cnt[i];
if (total >= k) {
return i + left_;
}
}
return -1;
}
};
class Solution {
private:
unique_ptr<NumberTracker> tracker;
public:
Solution() : tracker(make_unique<BucketSort>(-50, 50)) {}
vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
int n = nums.size();
vector<int> res;
for (int i = 0; i < k; i++) {
tracker->update(nums[i], 1);
}
int ans = tracker->findKth(x);
res.push_back(min(ans, 0));
for (int i = k; i < n; i++) {
tracker->update(nums[i-k], -1);
tracker->update(nums[i], 1);
ans = tracker->findKth(x);
res.push_back(min(ans, 0));
}
return res;
}
};
class FenwickTree : public NumberTracker {
private:
int left_;
int right_;
int n_;
vector<int> bit;
int lowbit(int a) {
return a & (-a);
}
void add(int idx, int diff) {
idx++;
int n = bit.size();
while (idx < n) {
bit[idx] += diff;
idx += lowbit(idx);
}
}
int query(int idx) {
int sum = 0;
idx++;
while (idx > 0) {
sum += bit[idx];
idx -= lowbit(idx);
}
return sum;
}
public:
FenwickTree(int left, int right) {
left_ = left;
right_ = right;
n_ = right - left + 1;
bit.assign(n_ + 1, 0);
}
void update(int num, int delta) {
num -= left_;
add(num, delta);
}
int findKth(int k) {
int left = 0;
int right = n_;
while (left < right) {
int mid = (left + right) >> 1;
if (query(mid) >= k)
right = mid;
else
left = mid + 1;
}
return min(0, left + left_);
}
};
class NumberTracker {
public:
virtual void build(vector<int> nums) = 0;
virtual void update(int num, int delta) = 0;
virtual int findKth(int k) = 0;
virtual ~NumberTracker() {}
};
class SegmentTree : public NumberTracker {
private:
int n_;
int m_;
vector<int> tree_;
unordered_map<int,int> num_to_idx;
unordered_map<int,int> idx_to_num;
int lowbit(int a) {
return a & (-a);
}
public:
SegmentTree() {}
void build(vector<int> nums) override {
sort(nums.begin(), nums.end());
for (int i = 0, j = 0; i < nums.size(); i++) {
if (i > 0 && nums[i] == nums[i-1]) continue;
num_to_idx[nums[i]] = j;
idx_to_num[j++] = nums[i];
}
for (n_ = 1; n_ < num_to_idx.size(); n_ <<= 1);
m_ = n_ << 1;
tree_.assign(m_, 0);
}
void update(int num, int delta) override {
int idx = num_to_idx[num];
idx += n_;
while (idx > 0) {
tree_[idx] += delta;
idx >>= 1;
}
}
int findKth(int k) override {
int idx = 1;
while (idx < n_) {
idx <<= 1;
if (tree_[idx] < k) {
k -= tree_[idx];
idx++;
}
}
return idx_to_num[idx - n_];
}
};
class Solution {
private:
unique_ptr<NumberTracker> tracker;
public:
Solution() : tracker(make_unique<SegmentTree>()) {}
vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
tracker->build(nums);
int n = nums.size();
vector<int> res;
for (int i = 0; i < k; i++) {
tracker->update(nums[i], 1);
}
int ans = tracker->findKth(x);
res.push_back(min(ans, 0));
for (int i = k; i < n; i++) {
tracker->update(nums[i-k], -1);
tracker->update(nums[i], 1);
ans = tracker->findKth(x);
res.push_back(min(ans, 0));
}
return res;
}
};