algorithm - 计算空间和时间复杂度并提高该程序的效率

Question

问题

在重复数字数组中查找非重复数字列表。

我的解决方案

   public static int[] FindNonRepeatedNumber(int[] input)
    {
        List<int> nonRepeated = new List<int>();
        bool repeated = false;

        for (int i = 0; i < input.Length; i++)
        {
            repeated = false;

            for (int j = 0; j < input.Length; j++)
            {
                if ((input[i] == input[j]) && (i != j))
                {
                    //this means the element is repeated.
                    repeated = true;
                    break;
                }
            }

            if (!repeated)
            {
                nonRepeated.Add(input[i]);
            }
        }

        return nonRepeated.ToArray();
    }

时间和空间复杂度时间复杂度 = O(n^2)空间复杂度 = O(n)

我不确定上面计算的时间复杂度，也不知道如何才能使这个程序更高效、更快速。

Answer 1

您提供的算法的复杂度为 O(n^2)。

使用Hashmaps改进算法。伪代码如下:

public static int[] FindNonRepeatedNumbers(int[] A)
{
Hashtable<int, int> testMap= new Hashtable<int, int>();

for (Entry<Integer, String> entry : testMap.entrySet()) {
            tmp=testMap.get(A[i]);
            testMap.put(A[i],tmp+1);
}

/* Elements that are not repeated are:

Set set = teatMap.entrySet(); 
// Get an iterator 
Iterator i = set.iterator(); 
// Display elements 
while(i.hasNext()) { 
Map.Entry me = (Map.Entry)i.next(); 
if(me.getValue() >1)
{
    System.out.println(me.getValue()); 
}
} 

操作:我在这里所做的是，我使用带有 keys 的 Hashmaps 将 hashmaps 作为输入数组的元素。 HashMap 的值 就像每个元素的计数器。因此，如果一个元素出现一次，则该键的值为 1，并且键值随后会根据输入数组中元素的重复出现而递增。

所以最后您只需检查您的 HashMap ，然后显示哈希值为 1 的元素，这些元素是未重复的元素。如果输入数组长度为 k，则此算法的时间复杂度是 O(k) 创建 hashmap 和 O(k) 搜索，如果输入数组长度是 k .这比 O(n^2) 快得多。最坏的情况是根本没有重复元素。伪代码可能很乱，但这种方法是我能想到的最好的方法。