从字符串中删除字符

Question

我有一个字符串，如下所示：

string Text = "012345678901234567890123456789";

同时有一个带有索引的List<int>

List<int> Indexes = new List<int>() { 2, 4, 7, 9, 15, 18, 23, 10, 1, 2, 15, 40 };

以下为限制条件：

• 列表中存在重复项
• 列表未排序
• 索引可能大于 Text.length

如何最佳地从文本中删除索引列表中的字符？

035681234679012456789

有比这更有效的方法吗？

foreach (int index in Indexes
                        .OrderByDescending(x => x)
                        .Distinct()
                        .Where(x => x < Text.Length))
{
    Text = Text.Remove(index, 1);
}

更新：以下是当前答案的基准测试结果（string长度为100,000个字符，List<int>长度为10,000）：

Gallant: 3.322 ticks
Tim Schmelter: 8.602.576 ticks
Sergei Zinovyev: 9.002 ticks
rbaghbanli: 7.137 ticks
Jirí Tesil Tesarík: 72.580 ticks

- Byyo

---

问题是为什么你需要这个列表呢？一开始就不能使用 HashSet<int> 吗？这样就不会有重复项，而且使用 Contains 进行查找的效率更高，时间复杂度为 O(1)。 - Tim Schmelter

Answer 1

这里是一个相对优雅的LINQ方法：

Text = new string(Text.Where((c, index) => !Indexes.Contains(index)).ToArray());

它使用重载的Enumerable.Where，该方法映射序列中项目的索引。

如果您想要最高效而不是最可读的方式，并且文本非常大，则可以使用HashSet<int>代替列表（它不允许重复项），并使用StringBuilder创建新字符串：

var indexSet = new HashSet<int>(Indexes); // either create from the list(as shown here) or use it without your list
var textBuilder = new StringBuilder(Text.Length);

for(int i = 0; i < Text.Length; i++)
    if (!indexSet.Contains(i))
        textBuilder.Append(Text[i]);
Text = textBuilder.ToString();

当然，您还可以在LINQ方法中使用 HashSet<int> 使它更有效率。

- Tim Schmelter

---

如果你在使用Linq方法中使用HashSet，那仍然是O(n)的时间复杂度。 - juharr

构建二叉树并不快速。无论你在循环中赢得了什么，你都会在构建二叉树时失去它。 - Riad Baghbanli

@Tim Schmelter，如果你的输入是HashSet - 那是一种假设，不是吗？OP明确指出Indexes是List<int>，而不是HashSet<int>。 - Riad Baghbanli

@rbaghbanli：你做了更多的假设。可能OP不知道HashSet类。此外，如果列表不经常更改，您还可以将集合保持为查找实例，而保留列表。然后，您可以在稍微增加一些内存成本的情况下获得性能提升。但是，即使OP知道它并且无法使用它，也值得提到它。在许多其他情况下，它将有助于提高性能。 - Tim Schmelter

可能是OP不知道HashSet类 - 假设一。 "如果列表不经常更改" - 假设二。所以，重复一位来自stackoverflow的人说：你正在做更多的假设。 - Riad Baghbanli

Answer 2

这样做会更快：

string Text = "012345678901234567890123456789";
List<int> Indexes = new List<int>() { 2, 4, 7, 9, 15, 18, 23, 10, 1, 2, 15, 40 };

HashSet<int> hashSet = new HashSet<int>(Indexes);

StringBuilder sb = new StringBuilder(Text.Length);
for (int i = 0; i < Text.Length; ++i)
{
    if (!hashSet.Contains(i))
    {
        sb.Append(Text[i]);
    }
}

string str = sb.ToString();

- Sergei Zinovyev

---

HashSet<int> hashSet = new HashSet<int>(Indexes) - 并不快速。 - Riad Baghbanli

@rbaghbanli 相比于 .OrderByDescending(x=>x).Distinct()，它速度更快。 - Taemyr

是的，但还有更快的解决方案。 - Riad Baghbanli

你在测试中是否包含了 HashSet 的创建，并且对哪些大小进行了基准测试？ - Riad Baghbanli

构建 HashSet 的时间复杂度为 O(n^2)。例如，可以在这里查看：https://dev59.com/xW_Xa4cB1Zd3GeqP1HS_ - Riad Baghbanli

一个for循环？为什么每个人都建议使用for循环？C#不是有一个列表的filter方法吗？ - cat

Answer 3

是的，参见下面的代码（它将仅对每个序列迭代一次）：

var map = new short[Text.Length];
foreach (var i in Indexes)
{
    if (i < text.Count)
        map[i] = 1;
}
Text = new string(Text.Where((c, i) => map[i] == 0).ToArray());

- Riad Baghbanli

---

通过调用 RemoveAt，您会更改数组的索引。因此，只有在从数组末尾开始使用索引并删除重复项时才起作用。这就是为什么 OP 使用 OrderByDescending 和 Distinct 的原因。 - juharr

根据原帖中的代码，这是期望的行为。 - Riad Baghbanli

我不确定构建二叉树是否是一个快速的过程。索引越长，构建哈希集合所需的时间就越长。 - Riad Baghbanli

同意，但这将与创建新的NullableObject具有相同的性能。如果OP同意输入字符串没有char == 0，那么我们可以使用0而不是null，这样会更快，因为不需要创建任何对象。这给了我一个想法。等一下！ - Riad Baghbanli

为什么 short 默认值为 0 要比 bool 默认值为 false 更明显？在我看来，bool 更好，因为你可以将数组命名为 isInList，然后执行 Where((c,i) => !isInList[i])。这样可以避免使用魔法数字。 - juharr

Answer 4

以下假设您的字符串包含一组已知的字符。如果您确定例如Unicode字符￰从不出现在字符串中，您可以使用它作为占位符来标记要删除的字符。尽管存在此限制，但这应该非常快速：

char temp = '\uFFF0';
StringBuilder sb = new StringBuilder(Text);
for (int i = 0; i < Indexes.Count; i++)
{
    if (Indexes[i] < sb.Length)
    {
        sb[Indexes[i]] = temp;
    }
}

Text = sb.Replace(temp.ToString(), null).ToString();

这似乎比其他答案中建立HashSet的方法快3-4倍。 http://ideone.com/mUILHg

---

如果你无法做出上述的假设，你可以建立一个数组来包含这个额外的数据，而不是使用唯一字符。这会进行两轮迭代(所以速度慢一些)，但它仍然具有O(n)的效率(通常比在迭代之前将索引放入哈希表中更快)。

bool[] exclude = new bool[Text.Length];
for (int i = 0; i < Indexes.Count; i++)
{
    if (Indexes[i] < exclude.Length)
    {
        exclude[Indexes[i]] = true;
    }
}
StringBuilder sb = new StringBuilder(Text.Length);
for (int i = 0; i < Text.Length; i++)
{
    if (!exclude[i])
    {
        sb.Append(Text[i]);
    }
}
Text = sb.ToString();

快速基准测试：http://ideone.com/3d2uPH

- Gallant

---

你为什么没有使用空字符？https://dev59.com/AHA65IYBdhLWcg3wuRF8 - Byyo

令人惊讶的是，字符数组给了我相同的速度：var a = Text.ToCharArray(); foreach (int i in Indexes) if (i < Text.Length) a[i] = ' '; var result = new string(a).Replace(" ", ""); - Slai

没关系..当“索引”比“字符”多时，字符数组对我来说更快，但当字符比“索引”多10倍或更多时，速度会变慢。 - Slai

@Byyo 这也可以工作，但有效的字符串可以包含空字符（即Unicode字符\u0000），因此问题仍然存在。 - Gallant

Answer 5

一种使用字节（可以替换为布尔）数组而不是哈希表的修改方案。优点：线性复杂度，缺点：需要额外的内存来存储标志数组。

string Text = "012345678901234567890123456789";
List<int> Indexes = new List<int>() { 2, 4, 7, 9, 15, 18, 23, 10, 1, 2, 15, 40 };
byte[] contains = new byte[Text.Length];
Indexes.ForEach(p=> {if ( p<Text.Length) contains[p]=1;});
var output = string.Concat(Enumerable.Range(0, Text.Length).Where(p => contains[p] != 1).Select(p => Text[p]));

- Jiří Tesil Tesařík

---

提供额外信息以澄清您的答案是一个好习惯，而不仅仅是发布代码。 - Phiter