C# 查找和为N的幸运子序列前10项:同长度元素降序排序实现问题
问题根源
你之前的实现偏差本质是对同长度排序规则的理解偏移:将“按子序列元素逐位降序比较”错等同于“按原数组中的起始索引先后排序”,而题目要求的同长度排序逻辑完全不涉及子序列在原数组的位置,只和子序列本身的元素内容有关。
正确实现方案
1. 定义Sequence类承载子序列,内置规则化比较逻辑
按照题目提示实现IComparable<Sequence>接口,把排序规则硬编码到比较方法中,完全避免外部排序逻辑的误用:
public class Sequence : IComparable<Sequence> { // 直接存储子序列的元素引用,不存储冗余的原数组索引 private readonly int[] _content; public int Length => _content.Length; public Sequence(int[] content) { _content = content; } public int CompareTo(Sequence? other) { if (other is null) return 1; // 第一优先级:子序列长度降序 if (this.Length != other.Length) { // 长度更长的子序列排序优先级更高,排得更靠前 return other.Length.CompareTo(this.Length); } // 第二优先级:同长度下从左到右逐元素降序比较 for (int i = 0; i < this.Length; i++) { if (this._content[i] != other._content[i]) { // 第一个不相等位置的元素值更大的子序列排前面 return other._content[i].CompareTo(this._content[i]); } } // 所有元素完全相等时,两个子序列排序优先级一致 return 0; } // 方便输出子序列内容的辅助方法 public override string ToString() => $"[{string.Join(", ", _content)}]"; }
2. 同长度排序的核心判断逻辑说明
对两个等长的幸运子序列S1、S2,比较规则等价于反向字典序比较:
- 从子序列的第一个元素开始逐位对比,找到第一个值不相等的位置
- 该位置上元素值更大的子序列,整体排序更靠前
- 整个比较过程完全不涉及子序列在原P数组中的起始位置、结束位置等元信息
举个对应测试用例的实际对比示例:
给定测试用例P = {1,1,2,1,-1,2,3,-1,1,2,3,5,1,-1,2,3},N=5,找到两个长度为4的幸运子序列:
- S1 = [1,1,2,1](从原数组索引0开始)
- S2 = [-1,1,2,3](从原数组索引7开始)
逐位比较时,第一个位置的1 > -1,因此S1排在S2前面,和S2在原数组中的位置无关。之前按起始索引升序排序的逻辑,会把位置更靠后的S2排到S1前面,和题目要求的规则完全相反,这就是结果偏差的核心来源。
3. 高性能Top10维护逻辑
按照题目提示,借助有序结构维护排序后的子序列,不需要存储所有幸运子序列再全量排序:
- 每找到一个新的幸运子序列,就把它插入到有序集合中
- 每次插入完成后,检查集合大小,如果超过10,直接移除集合中排序优先级最低的元素(也就是集合里排最末尾的那个)
- 遍历完所有可能的连续子数组后,集合中保留的就是最终需要输出的前10项
这种方式的内存占用始终只和Top10的大小有关,不会因为幸运子序列过多导致内存溢出,适配L最大50000的输入规模。
避坑提醒
- 不要额外存储原数组的起始索引作为同长度下的排序键,这是最常见的规则误解来源
- 逐元素比较时必须严格从左到右(即从子序列的第一个元素开始对比),不能从右往左比、也不能替换成元素和、元素乘积等其他统计指标
- 不要用
ArrayList作为子序列的存储类型,其元素访问效率低于原生int数组,会增加逐位比较的耗时
内容的提问来源于stack exchange,提问作者Yo Yeah
相关产品推荐
相关产品推荐

