长度为 t 的数组的所有元素都由 1 初始化。现在我们可以对数组执行两种类型的查询
- 将第
i 索引处的元素替换为 0 。此查询由 0 索引表示
- 查找并在新行打印一个整数，表示数组 A 中第 k 个
1 的索引；如果不存在这样的索引，则打印 -1。此查询由 1 k 表示
现在假设对于长度为 t=4 的数组，其开头的所有元素都是 [1,1,1,1] 现在用于查询 0 2 数组变为 [1,0,1,1] 并且查询 1 3 输出结果为 4/p>
我使用了蛮力方法，但如何使代码更高效？
n,q=4,2
arr=[1]*4
for i in range(q):
a,b=map(int,input().split())
if a==0:
arr[b-1]=0
else:
flag=True
count=0
target=b
for i,j in enumerate(arr):
if j ==1:
count+=1
if count==target:
print(i+1)
flag=False
break
if flag:
print(-1)
我也尝试过先将 1 的所有索引附加到列表中，然后进行二分查找，但是 pop 0 更改了索引，导致代码失败
def binary_search(low,high,b):
while(low<=high):
mid=((high+low)//2)
#print(mid)
if mid+1==b:
print(stack[mid]+1)
return
elif mid+1>b:
high=mid-1
else:
low=mid+1
n=int(input())
q=int(input())
stack=list(range(n))
for i in range(q):
a,b=map(int,input().split())
if a==0:
stack.pop(b-1)
print(stack)
else:
if len(stack)<b:
print(-1)
continue
else:
low=0
high=len(stack)-1
binary_search(low,high,b)
您可以构建一棵二叉树，其中每个节点都会为您提供其下方和左侧节点的数量。所以如果 n 是 7，那棵树最初看起来像这样(下面显示了所有的实际列表):
4
/ \
2 2
/ \ / \
1 1 1 1
----------------
1 1 1 1 1 1 1 -
将索引 4(从零开始)处的数组元素设置为 0，会将树更改为:
4
/ \
2 1*
/ \ / \
1 1 0* 1
----------------
1 1 1 1 0*1 1 -
因此，输入 0 表示 O(log(n)) 时间复杂度。
计算 1 的数量也可以在相同的时间复杂度下完成，方法是在沿正确的方向沿着树下降的同时对节点值求和。
这是您可以使用的 Python 代码。它代表 list in breadth-first order 中的树.我没有费尽心思进一步优化代码，但它具有上述时间复杂度:
class Ones:
def __init__(self, n): # O(n)
self.lst = [1] * n
self.one_count = n
self.tree = []
self.size = 1 << (n-1).bit_length()
at_left = self.size // 2
width = 1
while width <= at_left:
self.tree.extend([at_left//width] * width)
width *= 2
def clear_index(self, i): # O(logn)
if i >= len(self.lst) or self.lst[i] == 0:
return
self.one_count -= 1
self.lst[i] = 0
# Update tree
j = 0
bit = self.size >> 1
while bit >= 1:
go_right = (i & bit) > 0
if not go_right:
self.tree[j] -= 1
j = j*2 + 1 + go_right
bit >>= 1
def get_index_of_ith_one(self, num_ones): # O(logn)
if num_ones <= 0 or num_ones > self.one_count:
return -1
j = 0
k = 0
bit = self.size >> 1
while bit >= 1:
go_right = num_ones > self.tree[j]
if go_right:
k |= bit
num_ones -= self.tree[j]
j = j*2 + 1 + go_right
bit >>= 1
return k
def is_consistent(self): # Only for debugging
# Check that list can be derived by calling get_index_of_ith_one for all i
lst = [0] * len(self.lst)
for i in range(1, self.one_count+1):
lst[self.get_index_of_ith_one(i)] = 1
return lst == self.lst
# Example use
ones = Ones(12)
print('tree', ones.tree)
ones.clear_index(5)
ones.clear_index(2)
ones.clear_index(1)
ones.clear_index(10)
print('tree', ones.tree)
print('lst', ones.lst)
print('consistent = ', ones.is_consistent())
请注意，这会将索引视为从零开始的索引，而方法 get_index_of_ith_one 需要一个至少为 1 的参数(但它会返回一个从零开始的索引)。
它应该很容易适应您的需求。
复杂度
- 创建:O(n)
- 清除索引:O(logn)
- 获取一个的索引:O(logn)
- 空间复杂度:O(n)