改进去除元素的算法
问题
给定一个字符串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 ;
}
没有显示关键操作，而且其中一个（很可能是update方法）的成本与您想象的不同。 此外，你所说的复杂性保证是错误的，因为在某些时候你必须扫描至少为O(N)的字符串。
但无论如何，这里明显正确的策略是通过查询，按字符分开它们，然后以相反的顺序遍历查询，以找出要压制的字符的初始位置。 然后在字符串中穿过一次，只有在符合时才会发送字符。 这个解决方案，如果得到很好的实施，应该可以在O(N + M log(M)) 。
挑战是如何有效地表示删除。 我正在考虑某种相对偏移量的树，所以如果你发现第一次删除是3 a你可以有效地将它插入到树中，然后在每次删除之后移动它。 这是log(M)位的位置。