如何用约1.5n次比较在Rust中找出向量的最大和次大整数

一、修正数组分组逻辑（解决奇偶长度越界问题） #

• 遍历数组时采用步长为2的方式配对元素，循环范围覆盖从0到数组末尾：
  • 当当前索引i的下一个索引i+1小于数组长度时，取a[i]和a[i+1]配对比较
  • 若数组长度为奇数，最后一个无配对的元素直接加入较大数数组L
• 避免用n/2作为循环次数，改用step 2的迭代方式从根本上解决越界问题

二、正确构建L和S数组（解决元素分组错误） #

• 对每一对元素，严格将较大值放入L数组，较小值放入S数组，杜绝笔误（比如原代码中a[2*i*1]这类错误写法）
• 示例输入中的20未被正确加入L数组，就是因为分组逻辑的笔误，导致最大值丢失

三、确定最大值与次大值候选 #

1. 找出L数组的最大值max1：遍历L数组得到全局最大值
2. 收集次大值的所有候选：
   • 候选1：L数组中所有小于max1的元素里的最大值（如果L中有多个max1，则候选1可以是max1）
   • 候选2：S数组中的全局最大值
   • 候选3：所有与max1在配对时对应的S数组元素（比如如果max1是从(x, max1)配对中放入L的，那么x需要加入候选；如果是从(max1, x)配对中放入L的，x也需要加入候选）

四、计算最终结果 #

• 次大值是上述所有候选中的最大值
• 最终结果为max1 * 次大值

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