替代 O(N^2) 时间复杂度与 O(1) 空间复杂度，用于在数组中查找不同的值

Question

我正在尝试查看是否有任何替代蛮力算法（或对朴素蛮力算法略有改进/最差的性能）仍然会导致 O（N^2） 时间复杂度和 O（1） 辅助空间。

这是我的蛮力伪代码：

    procedure distinct(Input: array)                             
        for i=0 to i < length of array                      
            for j=i+1 to j < length of array                 
               if array[i] == array[j] and i != j then  
                  return false                        
               end if
               increment k
            end for
            increment j
        end for
        return true
    end procedure

我知道蛮力算法是一个糟糕的解决方案，有很多方法可以实现更好的性能（使用数据集或实现 O（N） 时间复杂度和 O（1） 空间复杂度），但是出于纯粹的兴趣，我试图找到 O（N^2） 最坏情况的时间复杂度和 O（1） 空间复杂度。甚至可能吗？

我在想我可能会应用排序算法（例如气泡或插入排序），然后使用 for 循环来遍历排序数组，但这仍然会给我一个二次函数而不是 O（N^3）？

Answer 1

使用堆排序对数组进行排序，并在找到两个相等的元素时停止：

• O（NLogN） 时间复杂度
• O（1） 空间复杂度

您也可以在此处查找其他（更高级的算法）

选择和插入排序是 2 种备选方案：

• O（NxN） 时间复杂度
• O（1） 空间复杂度