如何从List<Integer>中获取两个最小元素？解决代码超时问题

原问题 #

给定一个List<Integer>，想要取出其中两个最小的整数返回新列表。原思路是写辅助函数找最小值，主函数循环2次，每次移除当前最小值再找下一个加入新列表，但代码运行时因超时终止，原代码如下：

public static int countSorthelper(List<Integer> arr) {
    int temp = 0;
    int n = 0;
    while(n <= 2){
        for (int x = 0; x < arr.size(); x++){
            for (int y = x+1; y < arr.size() && y <= x+y; y++){
                if(arr.get(y) > arr.get(x)){
                    temp = arr.get(x);
                    n++;
                }
            }
        }
    }
    return temp;
}
public static List<Integer> countSort(List<Integer> arr){
    int n = 0;
    List<Integer> j = new ArrayList<>();
    while (n <= 2){
        countSorthelper(arr);
        arr.remove(countSorthelper(arr));
        j.add(countSorthelper(arr));
        n++;
    }
    return j;
}

问题根源 #

1. 辅助函数逻辑完全错误：
   • 内层循环的y <= x+y是恒成立的（y为正整数），但核心逻辑根本不是找最小值——判断arr[y] > arr[x]就把arr[x]赋值给temp，完全偏离找最小的需求；而且外层的while(n<=2)会让嵌套循环反复执行，n只有在满足条件时才递增，极易陷入死循环，这是超时的主要原因。
2. 主函数重复调用辅助函数：每次循环里调用3次countSorthelper，每次调用的结果可能不同（列表已被修改），导致移除和添加的元素逻辑混乱。
3. 循环次数错误：主函数while(n<=2)会循环3次（n=0、1、2），但我们只需要取2个元素。

修改后的代码 #

方案一：按原思路修复（找最小值+移除） #

先写正确的找最小值辅助函数，再修正主函数逻辑：

// 正确查找当前列表最小值的辅助函数
public static int findMin(List<Integer> arr) {
    int min = arr.get(0);
    for (int num : arr) {
        if (num < min) {
            min = num;
        }
    }
    return min;
}

// 主函数：取两个最小元素，不修改原列表
public static List<Integer> getTwoSmallest(List<Integer> arr) {
    // 复制原列表，避免修改传入的原始列表
    List<Integer> tempList = new ArrayList<>(arr);
    List<Integer> result = new ArrayList<>();
    
    // 循环2次，取两个最小值
    for (int i = 0; i < 2; i++) {
        int min = findMin(tempList);
        result.add(min);
        // 注意：要用Integer.valueOf包装，避免触发remove(int index)方法
        tempList.remove(Integer.valueOf(min));
    }
    
    return result;
}

方案二：更简洁的排序实现 #

如果不介意排序的时间开销，直接排序后取前两个元素，代码更简洁：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public static List<Integer> getTwoSmallest(List<Integer> arr) {
    List<Integer> tempList = new ArrayList<>(arr);
    Collections.sort(tempList);
    // 返回独立的新列表，避免返回subList的视图
    return new ArrayList<>(tempList.subList(0, 2));
}

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