给定整数数组，如何以O(nlog(n))复杂度判断是否存在等值元素？

核心思路 #

利用排序算法的O(nlogn)时间复杂度特性，排序后相同元素会相邻，只需一次线性遍历即可检测重复，整体时间复杂度为O(nlogn)。

具体实现步骤 #

• 排序数组：使用编程语言内置的O(nlogn)排序算法（如快速排序、归并排序）对目标数组进行排序，这一步是复杂度的主要来源。
• 遍历检查相邻元素：遍历排序后的数组，逐一比较当前元素与下一个元素是否相等。若发现相等元素，直接返回存在重复；遍历结束未发现则返回不存在。

代码示例 #

Python 实现

def has_duplicate(nums):
    sorted_nums = sorted(nums)
    for i in range(len(sorted_nums) - 1):
        if sorted_nums[i] == sorted_nums[i + 1]:
            return True
    return False

Java 实现

import java.util.Arrays;

public class DuplicateChecker {
    public static boolean hasDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }
}

另一种实现思路：平衡二叉搜索树 #

通过平衡二叉搜索树（如Java的TreeSet）存储元素，插入每个元素前检查是否已存在。插入和查找操作的时间复杂度均为O(logn)，n个元素的总复杂度为O(nlogn)。

Java 示例

import java.util.TreeSet;

public class DuplicateChecker {
    public static boolean hasDuplicate(int[] nums) {
        TreeSet<Integer> set = new TreeSet<>();
        for (int num : nums) {
            // add方法返回false表示元素已存在
            if (!set.add(num)) {
                return true;
            }
        }
        return false;
    }
}

复杂度说明 #

排序方案中，排序操作占O(nlogn)，遍历占O(n)，整体时间复杂度由排序主导，为O(nlogn)；平衡二叉搜索树方案中，n次O(logn)的插入/检查操作，总复杂度同样为O(nlogn)，均满足需求。

内容的提问来源于stack exchange，提问作者Domoro