c# - 从数组中查找第一个唯一数字

Question

我正在尝试使用 C# 回答测试，问题是从给定的 N 个整数数组 A 中找到第一个唯一数字。如果数组中没有唯一编号，则返回 -1。

例如，如果 A = {4,5,4,6,5,5,3,8,6} 则返回 3
如果 A = {3,2,3,2,3} 则返回 -1

数组A的每个元素的取值范围是[0..1,000,000,000]，N的取值范围是[1..100,000]，

预期的最坏情况时间复杂度 - O(N*Log(N))
预期的最坏情况空间复杂度 - O(N)，超出输入存储

我能够编写以下解决方案，该解决方案在遍历数组 A 时使用 List 变量存储重复数字。
我的问题如下:
1。该解决方案是否满足上述复杂性要求？
2.在不使用 LINQ 的情况下，是否有更好的方法/算法在 C# 中执行此操作？

 public int solution(int[] A)
    {

        if (A.Length == 1)
        {
            return A[0];
        }
        else if (A.Length == 2)
        {
            if (A[0] == A[1])
            {
                return -1;
            }
            else
            {
                return A[0];
              }
        }
        else
        {
            List<int> duplicateList = new List<int>();

            bool isDuplicate = false;
            for (int index = 0; index < A.Length - 1; index++)
            {                    
                if (duplicateList.IndexOf(A[index]) == -1)
                {
                    isDuplicate = false;
                    duplicateList.Add(A[index]);

                    for (int searchIndex = index + 1; searchIndex < A.Length; searchIndex++)
                    {
                        if (A[index] == A[searchIndex])
                        {
                            isDuplicate = true;
                        }
                        if (isDuplicate)
                        {
                            break;
                        }

                        if (searchIndex == A.Length - 1 && isDuplicate == false)
                        {
                            return A[index];
                        }
                    }

                }
            }

            if ((duplicateList.IndexOf(A[A.Length - 1])) == -1)
            {
                return A[A.Length - 1];
            }
            else return -1;
        }
    }

Answer 1

您的答案的时间复杂度为 O(n^2)，这可以很容易地从嵌套循环结构中推断出来，甚至更多取决于 List 中 indexOf 调用的实现。

因此优化到O(nlogn)可以使用C#中的Dictionary接口(interface)将数字及其出现频率和索引存储在数组中作为Key,Value对，然后遍历Dictionary 查找数组中频率为 1 的第一个数字。