在不使用java的情况下执行hasDuplicate数组方法.util退出吗?O(n)是可以实现的吗?

Question

我今天参加了一个面试，这个面试涉及到这个问题，为了扩大我的算法知识。我想看看是否有更好的建议。

我试图在不使用java的情况下找到数组中的重复项。在处理空间和时间复杂性方面，我的算法知识将会不断扩大。

以下是我在技术评估过程中生成的代码:

 public static boolean isThereDuplicates(int[] A){
    
    for (int i = 0; i < A.length; i++)
        for (int j = i + 1; j < A.length; j++){
            if (A[i] == A[j])
                return true;
        }
   
            return false;
}

这个简单的算法看起来与冒泡排序相同，它的运行时间为O(N^2)。有没有更好的算法可以用来实现这个?

Answer 1

如果A的值是合理的有限的(即你有足够的RAM)，你可以使用基数排序算法的骨架在O(n)中找到重复。

public static boolean containsDuplicates(int[] A)
{
    // Create a zero-initialised array the size of the maximum allowed value in A.
    int[] count = new int[maximumValuePossible(A)];
    for (int i = 0; i < A.length; i++)
    {
        if (count[A[i]] != 0)
        {
            // The value at A[i] is already in the histogram -> duplicate!
            return true;
        }
        // A[i] is not in the histogram yet.
        count[A[i]]++;
    }
    return false;
}

编辑:返回一个删除重复项的数组副本，你可以这样做:

public static int[] stripped(int[] A)
{
    int[] count = new int[maximumValuePossible(A)];
    int uniques = 0;
    for (int i = 0; i < A.length; i++)
    {
        count[A[i]]++;
        if (count[A[i]] == 1)
        {
            uniques++;
        }
    }
    if (uniques == 0) return null;
    int[] retArray = new int[uniques];
    int retIndex = 0;
    for (int i = 0; i < count.length; i++)
    {
        if (count[i] > 0)
        {
            retArray[retIndex++] = count[i];
        }
    }
    return retArray;
}

Answer 2

这个问题的SOP解决方案是通过哈希。也就是0 (n)，出于对james的尊重，它是基数排序算法的骨架(或者只是骨髓)。

Answer 3

您还可以使用任何O(nlogn)排序算法对数组进行排序，然后对排序后的数组进行线性扫描，以查看元素i和元素i+1是否相等。总运行时间为0 (nlogn)。空间复杂度取决于所使用的排序算法。