C++按奇偶排序数组自定义比较器触发TLE的原因求解
问题原因分析
C++标准库中的
std::sort对传入的自定义比较器有严格要求:必须满足**严格弱序(Strict Weak Ordering)**规则,违反该规则会触发未定义行为,超时、结果错误、程序崩溃均属于可能的异常表现。
第一个比较器的问题
第一个比较器的实现如下:
bool custom_cmp(int &l, int &r){ return l%2 == 0; }
该实现完全不参考右值r的属性,完全不满足严格弱序的核心要求:
- 若两个元素均为偶数:
custom_cmp(偶1, 偶2)返回true,custom_cmp(偶2, 偶1)也返回true,违反了「若cmp(a,b)为真,则cmp(b,a)必须为假」的互反规则 - 若两个元素均为奇数:
custom_cmp(奇1, 奇2)返回false,custom_cmp(奇2, 奇1)也返回false,同样不符合严格弱序的等价判断规则
上述问题会导致std::sort的内部排序逻辑(通常为快速排序变体)完全失效,最坏情况时间复杂度退化为O(n²),甚至可能陷入死循环,最终触发超时。
第二个比较器的合理性
第二个比较器的实现如下:
bool custom_cmp(int &l, int &r){ return (l%2 < r%2); }
偶数模2结果为0,奇数模2结果为1,该实现完全满足严格弱序要求:
- 左偶右奇:0 < 1 → 返回true,偶数排在奇数前,符合题目要求
- 左奇右偶:1 < 0 → 返回false,符合排序逻辑
- 两者同奇偶:
l%2 == r%2→ 返回false,排序逻辑会判定二者等价,顺序可任意
因此std::sort可以正常运行,时间复杂度稳定在O(nlogn),不会出现超时问题。
内容的提问来源于stack exchange,提问作者Raghav Gupta
相关产品推荐
相关产品推荐

