algorithm - 如何检查数组是否仅包含时间复杂度为 n logn 的不同元素

Question

到目前为止，我的工作是在时间复杂度为 n^2 的上面，任何人都可以帮助将效率提高到 nlogn 或以下吗？

    bool checkDuplicates( int array[], int n)
    {
     int i,j;
     for( i = 0; i < n; i++ )
     {
      for( j = i+1; j < n; j++ )
      {
       if( array[i] == array[j] )
        return true;
      }
     }
     return false;
    }

Answer 1

您可以对数组进行快速排序 (n log(n))，然后查找重复项变成线性的(只需要检查连续的元素)。