std::sort是否一定会比较相等值？用排序中断检测数组重复是否可靠？

回答 #

你的这段代码无法在所有符合C++标准的环境下稳定运行，主要有两个核心问题：

1. std::sort没有强制要求比较相等元素
   C++标准只要求std::sort最终输出的序列满足你传入的比较器定义的顺序，没有规定排序过程中必须对相等元素执行比较操作。很多实现会做针对性优化，比如针对整数数组的计数排序预处理、块排序的区间预判逻辑等，这些场景下相等元素根本不会进入你写的比较器，异常不会触发，代码会错误返回false。
2. 比较器抛异常属于未定义行为
   C++标准明确要求std::sort传入的比较器必须满足严格弱序要求，且不能抛出异常。在比较器内抛出异常后，排序的中间状态是不可控的，哪怕你在外层捕获了异常，也可能出现内存泄漏、程序崩溃、死循环等问题，你在LeetCode上测试通过只是刚好匹配了当前LeetCode环境的std::sort实现，换其他编译器或标准库版本就可能出问题。

推荐实现方案 #

你可以选择两种经过工程验证的常规写法：

• 排序后遍历相邻元素，时间复杂度O(nlogn)，空间复杂度O(1)（不计排序栈开销）

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] == nums[i-1]) return true;
        }
        return false;
    }
};

• 哈希表去重对比，时间复杂度O(n)，空间复杂度O(n)

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());
        return s.size() != nums.size();
    }
};

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