Problem

Given a string s and m queries. For each query delete the K -th occurrence of a character x .

For example:

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

Ans abbc

My approach

I am using BIT tree for update operation.

Code:

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));
}

Time Complexity is O(M log N) where N is length of string ss .

Question

My solution gives me Time Limit Exceeded Error . How can I improve it?

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 ;
}

---

There are key operations not shown, and odds are that one of them (quite likely the update method) has a different cost than you think. Furthermore your stated complexity is guaranteed to be wrong because at some point you have to scan the string which is at minimum O(N) .

But anyways the obviously right strategy here is to go through the queries, separate them by character, and then go through the queries in reverse order to figure out the initial positions of the characters to be suppressed. Then run through the string once, emitting characters only when it fits. This solution, if implemented well, should be doable in O(N + M log(M)) .

The challenge is how to represent the deletions efficiently. I'm thinking of some sort of tree of relative offsets so that if you find that the first deletion was 3 a you can efficiently insert it into your tree and move every later deletion after that one. This is where the log(M) bit will be.

链接地址: http://www.djcxy.com/p/24092.html

上一篇: Android倒数计时器圆形进度条与计时器不匹配

下一篇: 改进去除元素的算法