我有一个 N 个元素的数组 A 。我必须在其中执行 Q 查询。在每个查询中，我选择一个索引 I(0-based) 并执行以下操作
for j = I+1 to N:
if A[j]<A[i]:
A[j]=0
注意：查询不是相互独立的。
5 2
4 3 4 3 2
3 2
4 3 4 0 0
我尝试过需要 O(n*q) 的蛮力解决方案。这就是我所做的。
n,q = map(int,input().split())
A = list(map(int,input().split()))
query = list(map(int,input().split()))
for i in range(len(query)):
for j in range(query[i]+1,n):
if A[j]<A[query[i]]:
A[j] = 0
print(A)
我想在小于 O(n*q) 的时间内完成上述问题。是否有可能 。你能告诉我们使用哪种算法吗？
创建大小的辅助阵列N，其中每个元素将是1如果存在与值的查询i，或0，否则。
然后，我们可以迭代辅助数组并跟踪查询的最大值是多少x[i]。
在每个步骤（让命名current），如果这是最大超过当前元素的值，更新元件0-这意味着有一个与值的查询p，其中x[p] > x[current]，因此，x[current]被设定为0。
这样，我们实现的整体运行时间O(n + q)和O(n)内存。
让我们来看看这个例子：
n = 5
q = 2
x = {4, 3, 4, 3, 2}
q[0] = 3
q[1] = 2
最初，我们的辅助数组 a 将是a = {0, 0, 0, 0, 0}。
第一个查询是q[0] = 3，因此我们更新a[3] = 1，因为在x[3]必要时必须与之后的所有内容进行比较x[3]和更新。
第二个查询是q[1] = 2，因此我们更新a[2] = 1，因为在x[2]必要时必须与之后的所有内容进行比较x[2]和更新。现在，这重叠与以前的查询，以便将它们结合起来，并决定我们是否应该更新的元素0或不，我们要以最大的x[2]和x[3]。
最后，我们迭代a并跟踪查询的当前最大值x。我们更新x[i]为0if受任何查询的影响，其值小于影响它的查询的最大值。
我的代码是用 Java 编写的，但我希望它是不言自明的：
int n = in.nextInt(), q = in.nextInt();
int[] x = new int[n];
for (int i = 0; i < n; i++) {
x[i] = in.nextInt();
}
int[] a = new int[n];
while (q-- > 0) {
int i = in.nextInt();
a[i] = 1;
}
int max = 0;
for (int i = 0; i < n; i++) {
if (a[i] == 1) {
max = Math.max(max, x[i]);
}
if (x[i] < max) {
x[i] = 0;
}
}
for (int i = 0; i < n; i++) {
out.print(x[i]);
out.print(' ');
}
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句