从字符串中删除字符

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

更新:以下是当前答案的基准(string100.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

Answer 1

这是一种或多或少优雅的LINQ方式:

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

它使用的重载Enumerable.Where项目序列中项目的索引.

如果你想要最高效而不是最易阅读的方式并且文本非常大,你可以使用a HashSet<int>而不是不允许重复的列表和a 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();

当然,您也可以使用HashSet<int>LINQ方法来提高效率.

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

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

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