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

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(&nbsp; &nbsp; s => new { Stuff = s.Key, Count = s.Count() });var dictionary = groups.ToDictionary(g => g.Stuff, g => g.Count);取自此处或按照juharr 的建议O(n) 是最低要求，因为您必须至少检查所有名称一次。