改进元素删除算法

Question

问题

给定一个字符串 s 和 m 个查询。对于每个查询，删除字符 x 的第 K 次出现。

例如：

abcdbcaab
5
2 a
1 c
1 d
3 b
2 a

Ans abbc

我的方法

我使用BIT树进行更新操作。

代码：

for (int i = 0; i < ss.length(); i++) {

    char cc = ss.charAt(i);
    freq[cc-97] += 1;
    if (max < freq[cc-97]) max = freq[cc-97];
    dp[cc-97][freq[cc-97]] = i;                 // Counting the Frequency
}
BIT = new int[27][ss.length()+1];
int[] ans = new int[ss.length()];
int q = in.nextInt();
for (int i = 0; i < q; i++) {
    int rmv = in.nextInt();
    char c = in.next().charAt(0);

    int rr = rmv + value(rmv, BIT[c-97]);              // Calculating the original Index Value
    ans[dp[c-97][rr]] = Integer.MAX_VALUE;

    update(rmv, 1, BIT[c-97], max);            // Updating it
}
for (int i = 0; i < ss.length(); i++) {
    if (ans[i] != Integer.MAX_VALUE) System.out.print(ss.charAt(i));
}

时间复杂度为O(M log N)，其中N是字符串ss的长度。

问题

我的解决方案导致超时错误。我该如何改进它？

public static void update(int i , int value , int[] arr , int xx){  
    while(i <= xx){
        arr[i ]+= value;
        i += (i&-i);
    }
}

public static int value(int i , int[] arr){
    int ans = 0;

    while(i > 0){
        ans += arr[i];
        i -= (i &- i);
    }
    return ans ;
}

- user4392540

---

什么是BIT树？特别是，如何将int[][]解释为树？ - meriton

那么in是什么？如果它是java.util.Scanner的实例，那么它可能会太慢了。未缓冲的输出也可能是性能不佳的原因。 - kraskevich

为什么关于算法的问题被认为是与计算机科学无关的离题问题，只有关于语法的问题才被视为主题相关。 - user4392540

请问您能否添加完整的代码和n、m的限制条件？我认为问题可能出在输入/输出方面，但如果没有额外的信息，就无法确定。 - kraskevich

为了回答这个问题，我们需要理解你的代码，这非常困难。考虑使用更具描述性的名称（在代码完成时代，没有理由将名称限制为一个或两个字符），并添加注释（例如关于数据结构的不变量）。 - meriton

Answer 1

有关键操作未显示，很可能其中一个（很可能是update方法）的成本与您想象的不同。此外，您声明的复杂度保证是错误的，因为在某个时刻，您必须扫描字符串，其最小值为O（N）。

但无论如何，在这里显然正确的策略是遍历查询，按字符分离它们，然后按相反的顺序遍历查询，以找出要抑制的字符的初始位置。然后只有在符合条件时才运行一次字符串，发出字符。如果实现得好，这个解决方案应该可在O（N + M log（M））内完成。

挑战在于如何有效地表示删除。我正在考虑某种相对偏移量的树形结构，以便如果您发现第一个删除是3 a，则可以将其有效地插入到树中，并将每个后来的删除项移动到该删除项之后。这就是log（M）位的地方。

- btilly