arrays - 在数组中查找不同值的O(1)空间复杂度的O(N ^ 2)时间复杂度

我想看看是否有任何替代蛮力算法（或一个轻微的改进/最坏的性能，一个天真的暴力算法）仍然会导致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）空间复杂度。甚至可能吗？
我在想我可以应用排序算法（例如bubble或insertion sort），然后使用for循环遍历排序数组，但这是否仍然会给我一个二次函数而不是o（n^3）？

最佳答案

使用heapsort对数组排序，并在找到两个相等元素时停止：
O（NLogn）时间复杂度
O（1）空间复杂度
您还可以为此目的寻找其他（更高级的算法）here
选择和插入排序是两种可选方法：
O（NXN）时间复杂度
O（1）空间复杂度