0

问题

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

我的解决方案

   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)

我不确定上面计算的时间复杂度，以及如何使这个程序更高效和快速。

4

3 回答 3

2

您提供的算法的复杂性是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()); 
}
}

操作： 我在这里所做的是使用哈希映射，哈希映射的键是输入数组的元素。哈希图的值就像每个元素的计数器。因此，如果一个元素出现一次，则该键的值为 1，并且该键值随后根据输入数组中元素的重复出现递增。

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

于 2012-06-18T18:16:18.437 回答
0

时间复杂度 O(n) 意味着你不能有一个内循环。一个完整的内循环是 O(n^2)。

于 2012-06-18T17:29:59.937 回答
0

两个指针。开始和结束。当相同的字母到达时开始递增并存储开始和结束位置，长度以供参考......否则增加结束......继续这样做直到列表结束......比较所有输出，你应该有最长的连续唯一数字列表。我希望这是问题所要求的。线性算法。

void longestcontinuousunique(int arr[])
{
int start=0;
int end =0;
while (end! =arr.length())
{
if(arr[start] == arr[end])
{
start++;
savetolist(start,end,end-start);
}
else
end++
}

return maxelementof(savedlist);
    }
于 2012-06-18T17:51:10.073 回答