class Solution {
public:
int kBigIndices(vector<int>& nums, int k) {
}
};
2519. 统计 K-Big 索引的数量
给定一个 下标从0开始 的整数数组 nums 和一个正整数 k 。
如果满足以下条件，我们称下标 i 为 k-big ：
k 个不同的索引 idx1 ，满足 idx1 < i 且 nums[idx1] < nums[i] 。k 个不同的索引 idx2 ，满足 idx2 > i 且 nums[idx2] < nums[i] 。返回 k-big 索引的数量。
示例 1 ：
输入：nums = [2,3,6,5,2,3], k = 2 输出：2 解释：在nums中只有两个 2-big 的索引: - i = 2 --> 有两个有效的 idx1: 0 和 1。有三个有效的 idx2: 2、3 和 4。 - i = 3 --> 有两个有效的 idx1: 0 和 1。有两个有效的 idx2: 3 和 4。
示例 2 ：
输入：nums = [1,1,1], k = 3 输出：0 解释：在 nums 中没有 3-big 的索引
提示：
1 <= nums.length <= 1051 <= nums[i], k <= nums.length原站题解
java 解法, 执行用时: 22 ms, 内存消耗: 52.7 MB, 提交时间: 2023-10-21 19:53:39
class Solution {
int[]treeleft,treeright;//双树状数组
int n;
public int kBigIndices(int[] nums, int k) {
this.n=nums.length;
this.treeleft=new int[n+1];
this.treeright=new int[n+1];
for(int i:nums)update(treeright,i+1,1);//先初始化右边树
int ans=0;
for(int i:nums){
update(treeright,i+1,-1);//右边树去掉当前结点
if(query(treeright,i)>=k&&query(treeleft,i)>=k)ans++;//左右两边比i小的数，都满足条件
update(treeleft,i+1,1);//当前结点更新到左边树中
}
return ans;
}
public int low_bit(int x) {
return x & -x;
}
public void update(int[]tree, int x, int dt) {
while (x <=n) {
tree[x] += dt;
x += low_bit(x);
}
}
public int query(int[]tree, int x) {
int res = 0;
while (x>0) {
res += tree[x];
x -= low_bit(x);
}
return res;
}
}
python3 解法, 执行用时: 852 ms, 内存消耗: 24.2 MB, 提交时间: 2023-10-21 19:53:18
from sortedcontainers import SortedList
class Solution:
def kBigIndices(self, nums: List[int], k: int) -> int:
sl = SortedList()
arr = sorted(nums)
ans = 0
for x in nums:
a = sl.bisect_left(x)
b = bisect_left(arr, x)
if a >= k and b - a >= k:
ans += 1
sl.add(x)
return ans
python3 解法, 执行用时: 1280 ms, 内存消耗: 32.1 MB, 提交时间: 2023-10-21 19:53:04
class BIT:
def __init__(self, n):
self.n = n
self.a = [0] * (n + 1)
def lowbit(x):
return x & -x
def update(self, x):
while x <= self.n:
self.a[x] += 1
x += BIT.lowbit(x)
def query(self, x):
res = 0
while x:
res += self.a[x]
x -= BIT.lowbit(x)
return res
class Solution:
def kBigIndices(self, nums: List[int], k: int) -> int:
bit = BIT(n := len(nums))
ans, sm = 0, 0
c = defaultdict(list)
for i, x in enumerate(nums): c[x].append(i + 1)
for x in sorted(c):
for i in c[x]:
a = bit.query(i)
ans += int(sm - k >= a >= k)
for i in c[x]:
bit.update(i)
sm += len(c[x])
return ans
cpp 解法, 执行用时: 84 ms, 内存消耗: 38.8 MB, 提交时间: 2023-10-21 19:52:46
class BIT{
int n;
vector<int> tree;
int lowbit(int idx){
return idx & -idx;
}
public:
BIT(int n){
this->n = n;
tree.resize(n);
}
void add(int idx, int x){
for(int i = idx + 1; i <= n; i += lowbit(i)){
tree[i - 1] += x;
}
}
int get(int idx){
int ans = 0;
for(int i = idx + 1; i > 0; i -= lowbit(i)){
ans += tree[i - 1];
}
return ans;
}
};
class Solution {
public:
int kBigIndices(vector<int>& nums, int k) {
int n = nums.size();
if(k * 2 >= n){
return 0;
}
BIT left(n + 1), right(n + 1);
for(auto x : nums){
right.add(x, 1);
}
int ans = 0;
for(auto x : nums){
right.add(x, -1);
if(left.get(x - 1) >= k && right.get(x - 1) >= k){
ans++;
}
left.add(x, 1);
}
return ans;
}
};