在Java中高效查找列表中最小的两个元素

import java.util.ArrayList;
import java.util.List;
import java.util.Objects; // 导入Objects类，用于record的equals和hashCode方法

// 定义一个record来封装最小和次小元素
record Minimums(int smallest, int nextSmallest) {
    // 构造函数、equals、hashCode、toString等方法由record自动生成
    // 可以根据需要添加自定义方法，但对于简单数据载体通常不需要
}

public class FindTwoSmallestElements {

    /**
     * 在给定的整数列表中查找并返回最小的两个元素。
     * 该方法以线性时间复杂度 O(N) 完成操作。
     *
     * @param list 待查找的整数列表
     * @return 包含最小元素和次小元素的 Minimums 对象。
     *         如果列表为空，则 smallest 和 nextSmallest 都为 Integer.MAX_VALUE。
     *         如果列表只有一个元素，则 smallest 为该元素，nextSmallest 为 Integer.MAX_VALUE。
     */
    public static Minimums findSmallest(List<Integer> list) {
        // 初始化 min1 为最小元素，min2 为次小元素
        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;

        // 遍历列表中的每一个值
        for (int val : list) {
            // 如果当前值小于 min1，说明找到了新的最小元素
            if (val < min1) {
                min2 = min1; // 原来的 min1 变为次小元素
                min1 = val;  // 更新 min1 为当前值
            } 
            // 否则，如果当前值小于 min2 (但大于或等于 min1)，说明找到了新的次小元素
            else if (val < min2) {
                min2 = val; // 更新 min2 为当前值
            }
            // 打印追踪信息，方便理解算法执行过程
            System.out.printf("当前值 = %2d : 最小元素 = %2d, 次小元素 = %2d%n", val, min1, min2);
        }
        return new Minimums(min1, min2);
    }

    public static void main(String[] args) {
        List<Integer> list1 = List.of(1, 10, 2, 5, 10, -2, 22, 3, -1);
        System.out.println("处理列表: " + list1);
        Minimums mins1 = findSmallest(list1);
        System.out.println("\n结果: " + mins1); // record会自动生成toString方法

        System.out.println("\n---");

        List<Integer> list2 = List.of(5, 5, 1, 1, 8, 2);
        System.out.println("处理列表: " + list2);
        Minimums mins2 = findSmallest(list2);
        System.out.println("\n结果: " + mins2);

        System.out.println("\n---");

        List<Integer> list3 = List.of(7); // 单个元素列表
        System.out.println("处理列表: " + list3);
        Minimums mins3 = findSmallest(list3);
        System.out.println("\n结果: " + mins3);

        System.out.println("\n---");

        List<Integer> list4 = new ArrayList<>(); // 空列表
        System.out.println("处理列表: " + list4);
        Minimums mins4 = findSmallest(list4);
        System.out.println("\n结果: " + mins4);
    }
}

处理列表: [1, 10, 2, 5, 10, -2, 22, 3, -1]
当前值 =  1 : 最小元素 =  1, 次小元素 = 2147483647
当前值 = 10 : 最小元素 =  1, 次小元素 = 10
当前值 =  2 : 最小元素 =  1, 次小元素 =  2
当前值 =  5 : 最小元素 =  1, 次小元素 =  2
当前值 = 10 : 最小元素 =  1, 次小元素 =  2
当前值 = -2 : 最小元素 = -2, 次小元素 =  1
当前值 = 22 : 最小元素 = -2, 次小元素 =  1
当前值 =  3 : 最小元素 = -2, 次小元素 =  1
当前值 = -1 : 最小元素 = -2, 次小元素 = -1

结果: Minimums[smallest=-2, nextSmallest=-1]

---
处理列表: [5, 5, 1, 1, 8, 2]
当前值 =  5 : 最小元素 =  5, 次小元素 = 2147483647
当前值 =  5 : 最小元素 =  5, 次小元素 =  5
当前值 =  1 : 最小元素 =  1, 次小元素 =  5
当前值 =  1 : 最小元素 =  1, 次小元素 =  1
当前值 =  8 : 最小元素 =  1, 次小元素 =  1
当前值 =  2 : 最小元素 =  1, 次小元素 =  2

结果: Minimums[smallest=1, nextSmallest=1]

---
处理列表: [7]
当前值 =  7 : 最小元素 =  7, 次小元素 = 2147483647

结果: Minimums[smallest=7, nextSmallest=2147483647]

---
处理列表: []
结果: Minimums[smallest=2147483647, nextSmallest=2147483647]