0

我想要一种算法从 O(n) 复杂度或更低复杂度的字符串中删除所有出现的给定字符？（它应该是 INPLACE 只编辑原始字符串）

例如。

String="aadecabaaab";

removeCharacter='a'

Output:"decbb"
4

7 回答 7

3

享受算法：

j = 0
for i in length(a):
  if a[i] != symbol:
    a[j] = a[i]
    j = j + 1

敲定：

length(a) = j
于 2013-08-08T20:53:33.020 回答
1

你不能用 a 来做，String因为它是不可变的，但是这里有一个 O(n) 算法可以用 a 来做char[]：

char[] chars = "aadecabaaab".toCharArray();
char removeCharacter = 'a';
int next = 0;
for (int cur = 0; cur < chars.length; ++cur) {
    if (chars[cur] != removeCharacter) {
        chars[next++] = chars[cur];
    }
}
// chars[0] through chars[4] will have {d, e, c, b, b} and next will be 5
System.out.println(new String(chars, 0, next));
于 2013-08-08T20:50:01.223 回答
1

严格来说，您不能从 a 中删除任何内容，String因为String该类是不可变的。但是您可以构建另一个String具有String除“要删除的字符”之外的所有字符的原始字符。

创建一个StringBuilder. 循环遍历原始 中的所有字符String。如果当前字符不是要删除的字符，则将其附加到StringBuilder. 循环结束后，将 转换StringBuilder为String.

于 2013-08-08T20:42:51.703 回答
0 
import java.util.*;
import java.io.*;

public class removeA{
  public static void main(String[] args){
    String text = "This is a test string! Wow abcdefg.";
    System.out.println(text.replaceAll("a",""));
  }
}
于 2013-08-08T20:52:45.297 回答
0

是的。在线性时间内，遍历字符串，使用 .charAt() 检查是否是 removeCharacter，不要将其复制到新字符串。如果没有，请复制。而已。

于 2013-08-08T20:44:16.350 回答
0

这可能不应该有“java”标签，因为在 Java 中，字符串是不可变的，你不能在适当的位置编辑它。对于更一般的情况，如果您有一个字符数组（使用任何编程语言）并且想要“就地”修改数组而不创建另一个数组，那么使用两个索引就很容易了。一个遍历数组中的每个字符，另一个从开头开始，仅当您看到不是 removeCharacter 的字符时才递增。由于我认为这是一项家庭作业，我将把它留在那里，让你弄清楚细节。

于 2013-08-08T20:46:55.110 回答
0

使用哈希表来保存要删除的数据。log N 复杂度。

std::string toRemove = "ad";
std::map<char, int> table;
size_t maxR = toRemove.size();  
for (size_t n = 0; n < maxR; ++n)
{
    table[toRemove[n]] = 0;
}

然后解析整个字符串并在命中时删除（字符串是一个数组）：

size_t counter = 0; 
while(thestring[counter] != 0)
{       
    std::map<char,int>::iterator iter = table.find(thestring[counter]);
    if (iter == table.end()) // we found a valid character!
    {
        ++counter;
    }
    else
    {
        // move the data - dont increment counter
        memcpy(&thestring[counter], &thestring[counter+1], max-counter);
        // dont increment counter
    }
}

编辑：我希望这不是技术测试或类似的东西。=S

于 2013-08-08T20:48:38.283 回答