在数组中查找特定字符串的所有索引的更快方法

Question

下面的代码用于查找在数组中可能只出现一次的字符串的所有索引，但代码不是很快。有人知道在数组中查找唯一字符串的更快更有效的方法吗？using System;using System.Collections.Generic;using System.Linq;public static class EM{    // Extension method, using Linq to find indices.    public static int[] FindAllIndicesOf<T>(this IEnumerable<T> values, T val)    {        return values.Select((b,i) => Equals(b, val) ? i : -1).Where(i => i != -1).ToArray();    }}public class Program{    public static string FindFirstUniqueName(string[] names)    {        var results = new List<string>();        for (var i = 0; i < names.Length; i++)        {            var matchedIndices = names.FindAllIndicesOf(names[i]);            if (matchedIndices.Length == 1)            {                results.Add(names[matchedIndices[0]]);                break;            }        }        return results.Count > 0 ? results[0] : null;    }    public static void Main(string[] args)    {        Console.WriteLine("Found: " + FindFirstUniqueName(new[]            {                "James",                "Bill",                "Helen",                "Bill",                "Helen",                "Giles",                "James",            }        ));    }}

Answer 1

您的解决方案具有 O(n^2) 复杂度。您可以使用 Hash-Map 将其改进为 O(n)。

考虑一个哈希映射，其中每个名称都有原始列表中的重复次数。现在你要做的就是检查字典中的所有键（又名哈希映射）并返回所有等于 1 的值。注意检查字典中的所有键小于 o(n) 因为它不能容纳大于 n名称。

要在 C# 中实现此字典，请执行以下操作：

List<string> stuff = new List<string>();

var groups = stuff.GroupBy(s => s).Select(

    s => new { Stuff = s.Key, Count = s.Count() });

var dictionary = groups.ToDictionary(g => g.Stuff, g => g.Count);

取自此处或按照juharr 的建议

O(n) 是最低要求，因为您必须至少检查所有名称一次。