Java: Tìm Min, Max, Second Min, Second Max trong mảng

Cho một mảng số nguyên, tìm: phần tử nhỏ nhất, lớn nhất, nhỏ thứ 2, lớn thứ 2.

Cách 1: Sắp xếp rồi lấy index (Đơn giản, O(n log n))

import java.util.Arrays;

public class Demo {
    public static void main(String[] args) {
        int[] arr = {55, 10, 8, 90, 43, 87, 95, 25, 50, 12};
        
        System.out.println("Mảng gốc: " + Arrays.toString(arr));
        
        Arrays.sort(arr); // Sắp xếp tăng dần
        
        System.out.println("Mảng sorted: " + Arrays.toString(arr));
        
        // LƯU Ý: Code gốc có BUG: in arr[0] cho cả smallest VÀ 2nd smallest
        // Sửa đúng:
        System.out.println("Smallest: " + arr[0]);
        System.out.println("2nd Smallest: " + arr[1]);        // Sửa: arr[1] không phải arr[0]
        System.out.println("Largest: " + arr[arr.length - 1]);
        System.out.println("2nd Largest: " + arr[arr.length - 2]);
    }
}

Kết quả (đã sửa)

Mảng gốc: [55, 10, 8, 90, 43, 87, 95, 25, 50, 12]
Mảng sorted: [8, 10, 12, 25, 43, 50, 55, 87, 90, 95]
Smallest: 8
2nd Smallest: 10
Largest: 95
2nd Largest: 90

Cách 2: Duyệt một lần (Single Pass - O(n), tối ưu)

Không cần sắp xếp, chỉ duyệt 1 lần, cập nhật 4 biến.

public class SinglePassDemo {
    public static void main(String[] args) {
        int[] arr = {55, 10, 8, 90, 43, 87, 95, 25, 50, 12};
        
        if (arr.length < 2) {
            System.out.println("Mảng cần ít nhất 2 phần tử");
            return;
        }
        
        // Khởi tạo
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE;
        
        for (int x : arr) {
            // Cập nhật min
            if (x < min1) {
                min2 = min1;
                min1 = x;
            } else if (x < min2 && x != min1) { // x != min1 để xử lý duplicate
                min2 = x;
            }
            
            // Cập nhật max
            if (x > max1) {
                max2 = max1;
                max1 = x;
            } else if (x > max2 && x != max1) {
                max2 = x;
            }
        }
        
        System.out.println("Smallest: " + min1);
        System.out.println("2nd Smallest: " + (min2 == Integer.MAX_VALUE ? "N/A (all same)" : min2));
        System.out.println("Largest: " + max1);
        System.out.println("2nd Largest: " + (max2 == Integer.MIN_VALUE ? "N/A (all same)" : max2));
    }
}

Kết quả

Smallest: 8
2nd Smallest: 10
Largest: 95
2nd Largest: 90

Cách 3: Sắp xếp thủ công (Bubble Sort - O(n²), chỉ để học)

public class BubbleSortDemo {
    public static void main(String[] args) {
        int[] arr = {55, 10, 8, 90, 43, 87, 95, 25, 50, 12};
        int n = arr.length;
        
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        
        System.out.println("Smallest: " + arr[0]);
        System.out.println("2nd Smallest: " + arr[1]);
        System.out.println("Largest: " + arr[n - 1]);
        System.out.println("2nd Largest: " + arr[n - 2]);
    }
}

Xử lý trường hợp đặc biệt

Code xử lý hoàn chỉnh (trả về Optional)

import java.util.OptionalInt;

public class MinMaxFinder {
    public static MinMaxResult findMinMax(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new MinMaxResult(OptionalInt.empty(), OptionalInt.empty(), 
                                    OptionalInt.empty(), OptionalInt.empty());
        }
        
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE;
        boolean hasMin2 = false, hasMax2 = false;
        
        for (int x : arr) {
            // Min
            if (x < min1) {
                min2 = min1; hasMin2 = (min1 != Integer.MAX_VALUE);
                min1 = x;
            } else if (x > min1 && (x < min2 || !hasMin2)) {
                min2 = x; hasMin2 = true;
            }
            
            // Max
            if (x > max1) {
                max2 = max1; hasMax2 = (max1 != Integer.MIN_VALUE);
                max1 = x;
            } else if (x < max1 && (x > max2 || !hasMax2)) {
                max2 = x; hasMax2 = true;
            }
        }
        
        return new MinMaxResult(
            OptionalInt.of(min1),
            hasMin2 ? OptionalInt.of(min2) : OptionalInt.empty(),
            OptionalInt.of(max1),
            hasMax2 ? OptionalInt.of(max2) : OptionalInt.empty()
        );
    }
    
    static class MinMaxResult {
        final OptionalInt min, secondMin, max, secondMax;
        MinMaxResult(OptionalInt min, OptionalInt secondMin, OptionalInt max, OptionalInt secondMax) {
            this.min = min; this.secondMin = secondMin; this.max = max; this.secondMax = secondMax;
        }
    }
}

Khuyến nghị

• Mảng nhỏ (< 1000 phần tử): Dùng Arrays.sort() - code ngắn, dễ đọc, đủ nhanh.
• Mảng lớn / Real-time / Embedded: Duyệt 1 lần (Single Pass) - O(n), không allocate mảng phụ.
• Stream API: IntStream.of(arr).distinct().sorted() rồi lấy first/last - nhưng tốn memory.