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

Question

我正在尝试查看是否有任何替代蛮力算法的方法（或者 improvement/worst 对天真的蛮力算法的轻微性能）仍然会导致 O(N^2) 时间复杂度和O(1)辅助space.

这是我的暴力伪代码：

    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) space 复杂度），但是出于纯粹的兴趣，我试图找到 O(N^2) 最坏情况时间复杂度和 O(1) space 复杂度。有可能吗？

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

Answer 1

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

O(NLogN) 时间复杂度
O(1) space 复杂度

您还可以为此寻找其他（更高级的算法）here

选择排序和插入排序是两种选择：

O(NxN) 时间复杂度
O(1) space 复杂度

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

Alternative O(N^2) time complexity with O(1) space complexity for finding distinct values in array

arrays

algorithm

sorting

distinct-values