比较唯一数组元素检查算法

• 下载源代码 - 17.37 KB

引言

我们如何判断一个列表是否包含重复元素？换句话说，我们如何知道列表中的所有元素都是唯一的？

有一些算法可以找出这一点。在本文中，我将解释其中的两种。

方法 1：逐个元素比较

这应该是最简单的方法。您要做的就是将列表中的所有元素与其他元素进行比较，一旦您找到任何一对相等的元素，您就知道数组元素不是唯一的。执行此操作的代码如下

public static bool IsUniqueSlow(IList<T> arrs)
{
    for (int i = 0; i < arrs.Count; i++)
    {
        for (int j = i + 1; j < arrs.Count; j++)
        {
            if (arrs[ i].Equals(arrs[j]))
                return false;
        }
    }
    return true;
}

非常简单，非常容易，不需要太多思考。如果您的列表不太大，这应该是显而易见的选择。

此方法的唯一问题是它的运行时间为 Ò(n²)。当列表变得非常大时，这绝对是不可接受的。因此，我们需要一种替代方法来减少运行时间。

方法 2：排序并比较

这种方法有点复杂。您不必进行逐个元素的比较，而是先对列表进行排序，然后再比较第¡^个元素和第 (¡+1)^个元素，以查看它们是否相等，如果相等，那么您知道您的数组包含重复的元素。如果您对列表中的所有元素重复此操作并且没有相等元素，那么您就知道这些元素都是唯一的。这是执行此操作的代码

public static bool IsUniqueFast(List<T> arrs)
{
    List<T> arrCopy = arrs.ConvertAll<T>(delegate(T tf) { return tf; });
    arrCopy.Sort();
    for (int i = 0; i < arrCopy.Count-1; i++)
    {
        if (arrCopy[i].Equals(arrCopy[i + 1]))
            return false;
    }
    return true;
} 

该代码应该是不言自明的。代码的第一行是创建原始列表的副本，以便在完成排序后，原始列表不会受到干扰。

让我们稍微分析一下这种方法的运行时间特性。排序算法的运行时间为Ò(nlogn)，比较循环的运行时间为Ò(n)。将时间加在一起，此方法的运行时间为Ò(nlogn)——比上一种方法有了显着改进。对于小列表，可能看不到性能差异，但如果列表很大，那么性能差异可能会使优点倾向于第二种方法。

测试运行结果

我们比较了这两种方法在两种情况下的性能，一种是当所有元素都是唯一的，另一种是当存在重复元素时。元素数量足够大，以便两种方法的运行时间至少为毫秒级。这是代码

private static void IsUniqueRun()
{
    int nOfList = 1 * ((int)Math.Pow(10, 4));
    List<int> myList = new List<int>();
    for (int i = 0; i < nOfList; i++)
        myList.Add(i);
        
    DateTime dtStart = DateTime.Now;
    Console.WriteLine("Does this array contain duplicated items? "
		+ArrayCheck<int>.IsUniqueSlow(myList));
    Console.WriteLine("Time taken for slow method " + 
		(DateTime.Now - dtStart).TotalMilliseconds);
    
    DateTime dtStart1 = DateTime.Now;
    Console.WriteLine("Does this array contain duplicated items? " 
		+ ArrayCheck<int>.IsUniqueFast(myList));
    Console.WriteLine("Time taken for fast method " + 
		(DateTime.Now - dtStart1).TotalMilliseconds);
}

private static void IsNotUniqueRun()
{
    int nOfList = 1 * ((int)Math.Pow(10, 4));
    List<int> myList = new List<int>();
    for (int i = 0; i < nOfList; i++)
        myList.Add(i);
    myList.Add(myList[myList.Count - 1]/2);
    DateTime dtStart = DateTime.Now;
    Console.WriteLine("Does this array contain duplicated items? " + 
		ArrayCheck<int>.IsUniqueSlow(myList));
    Console.WriteLine("Time taken for slow method " + 
		(DateTime.Now - dtStart).TotalMilliseconds);
    
    DateTime dtStart1 = DateTime.Now;
    Console.WriteLine("Does this array contain duplicated items? " + 
		ArrayCheck<int>.IsUniqueFast(myList));
    Console.WriteLine("Time taken for fast method " + 
		(DateTime.Now - dtStart1).TotalMilliseconds);
} 

结果呢？毫不奇怪，第二种方法的性能远远优于第一种方法，以下是结果

Does this array contain duplicated items? True
Time taken for slow method 1531.299
Does this array contain duplicated items? True
Time taken for fast method 15.6255
Does this array contain duplicated items? False
Time taken for slow method 1187.538
Does this array contain duplicated items? False
Time taken for fast method 0
Press any key to continue . . .

动机

我知道，我知道，想出上述算法并不难。但尽管它看起来很琐碎，但互联网上似乎没有明确的代码可以进行快速元素唯一性搜索。本文旨在填补这一空白，并为该目的提供一种可用的方法。

历史

• 首次编写于 2007 年 11 月 8 日