You need to enable JavaScript to run this app. C++按奇偶排序数组自定义比较器触发TLE的原因求解
优惠活动
大模型
产品
解决方案
定价
更多

C++按奇偶排序数组自定义比较器触发TLE的原因求解

问题原因分析

C++标准库中的std::sort对传入的自定义比较器有严格要求:必须满足**严格弱序(Strict Weak Ordering)**规则,违反该规则会触发未定义行为,超时、结果错误、程序崩溃均属于可能的异常表现。


第一个比较器的问题

第一个比较器的实现如下:

bool custom_cmp(int &l, int &r){
    return l%2 == 0;
}

该实现完全不参考右值r的属性,完全不满足严格弱序的核心要求:

  1. 若两个元素均为偶数:custom_cmp(偶1, 偶2)返回true,custom_cmp(偶2, 偶1)也返回true,违反了「若cmp(a,b)为真,则cmp(b,a)必须为假」的互反规则
  2. 若两个元素均为奇数: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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.18 01:15:04