Tìm số lớn thứ 2 trong mảng – Java code

Bài toán: Cho một mảng số nguyên, viết một chương trình tìm ra số lớn thứ 2 trong mảng.

Ví dụ

Input: arr[] = {12, 35, 1, 10, 34, 1}
Output: Phần tử lớn thứ 2 là 34.

Input: arr[] = {10, 5, 10}
Output: Phần tử lớn thứ 2 là 5.

Input: arr[] = {10, 10, 10}
Output: Không tồn tại phần tử lớn thứ 2 trong mảng

Đây có lẽ là bài toán chắc hẳn nhiều bạn sinh viên sẽ gặp phải trong quá trình học hoặc phỏng vấn xin việc. Trong bài viết này chúng ta sẽ cùng nhau tìm ra một số cách giải cho bài toán này sử dụng ngôn ngữ Java.

Cách 1 – Sắp xếp

Bài này cách giải đơn giản nhất chúng ta có thể làm đó là sắp xếp mảng giảm dần, sau đó lấy ra số lớn thứ 2 trong mảng. Cần lưu số số lớn thứ 2 phải là số có giá trị khác so với số lớn nhất nằm ở vị trí đầu tiên của mảng đã được sắp xếp.

 

import java.util.Arrays;

public class Main {

    static void print2largest(int arr[], int arr_size) {
        int i;

        if (arr_size < 2) {
            System.out.printf("Khong ton tai phan tu lon thu 2");
            return;
        }

        Arrays.sort(arr);

        for (i = arr_size - 2; i >= 0; i--) {
            if (arr[i] != arr[arr_size - 1]) {
                System.out.printf("Phan tu lon thu 2: " + arr[i]);
                return;
            }
        }

        System.out.printf("Khong ton tai phan tu lon thu 2");
    }

    public static void main(String[] args) {
        int arr[] = {12, 35, 1, 10, 34, 1};
        int n = arr.length;
        print2largest(arr, n);
    }
}

Output

Phan tu lon thu 2: 34

Độ phức tạp của phương pháp này: Time Complexity: O(n log n).

Duyệt mảng 2 lần

Phương pháp này hoạt động hiệu quả hơn cách đầu tiên, chúng ta sẽ phải duyệt mảng 2 lần. Trong lần đầu tiên chúng ta sẽ tìm ra phần tử lớn nhất. Trong lần duyệt thứ hai, chúng ta lại tìm phần tử lớn nhất trong các phần tửcòn lại, loại trừ phần tử lớn nhất trước đó.

public class Main {

    static void print2largest(int arr[], int arr_size) {
        int i, second;

        if (arr_size < 2) {
            System.out.printf(" Khong hop le");
            return;
        }

        int largest = second = Integer.MIN_VALUE;

        // Tìm phần tử lớn nhất
        for (i = 0; i < arr_size; i++) {
            largest = Math.max(largest, arr[i]);
        }

        // Tìm phần tử lớn nhất trong các phần tử còn lại, loại trừ largest
        for (i = 0; i < arr_size; i++) {
            if (arr[i] != largest)
                second = Math.max(second, arr[i]);
        }
        if (second == Integer.MIN_VALUE)
            System.out.println("Khong ton tai phan tu lon thu 2");
        else
            System.out.println("Phan tu lon thu 2: " + second);

    }

    public static void main(String[] args) {
        int arr[] = {12, 35, 1, 10, 34, 1};
        int n = arr.length;
        print2largest(arr, n);
    }
}

Output

Phan tu lon thu 2: 34

Độ phức tạp của phương pháp này: Time Complexity: O(n).

Duyệt mảng một lần

So với cách trên thì đây là cách hiệu quả nhất vì chúng ta chỉ tốn 1 lần duyệt mảng. Thứ tự triển khai sẽ như sau

1, Khởi tạo biến first = second = Integer.MIN_VALUE
2, Duyệt mảng
    + Nếu phần tử hiện tại arr[i] > first =>  second = first, first = arr[i]
    + Nếu phần tử hiện tại first < arr[i] < second => second = arr[i]
3, trả về second  

Triển khai mã Java

public class Main {

    static void print2largest(int arr[], int arr_size) {
        int i, first, second;

        if (arr_size < 2) {
            System.out.print(" Khong hop le ");
            return;
        }

        first = second = Integer.MIN_VALUE;
        for (i = 0; i < arr_size; i++) {
            if (arr[i] > first) {
                second = first;
                first = arr[i];
            }

            if (arr[i] < first && arr[i] > second) {
                second = arr[i];
            }
        }

        if (second == Integer.MIN_VALUE)
            System.out.print("Khong ton tai phan tu lon thu 2 ");
        else
            System.out.print("Phan tu lon thu 2: " + second);

    }

    public static void main(String[] args) {
        int arr[] = {12, 35, 1, 10, 34, 1};
        int n = arr.length;
        print2largest(arr, n);
    }
}

Độ phức tạp của phương pháp này: Time Complexity: O(n log n).