Bài toán: cho 1 mảng số nguyên, viết một công tác tìm ra số lớn thứ 2 trong mảng.

Bạn đang xem: Tìm phần tử lớn thứ 2 trong mảng

Ví dụ

Input: arr<> = 12, 35, 1, 10, 34, 1Output: bộ phận lớn thứ 2 là 34.Input: arr<> = 10, 5, 10Output: phần tử lớn thứ hai là 5.Input: arr<> = 10, 10, 10Output: không tồn tại phần tử lớn thứ hai trong mảngĐây chắc hẳn rằng là bài bác toán chắc hẳn nhiều chúng ta sinh viên sẽ chạm mặt phải trong quá trình học hoặc chất vấn xin việc. Trong bài viết này họ sẽ cùng mọi người trong nhà tìm ra một trong những cách giải cho việc này sử dụng ngôn từ Java.

Cách 1 – sắp tới xếp

Bài này cách giải đơn giản và dễ dàng nhất bạn có thể làm đó là thu xếp mảng giảm dần, sau đó lấy ra số lớn thứ hai trong mảng. Yêu cầu lưu số số lớn thứ hai phải là số có giá trị không giống so cùng với số lớn số 1 nằm làm việc vị trí thứ nhất của mảng vẫn được sắp tới xếp.

import java.util.Arrays;public class Main static void print2largest(int arr<>, int arr_size) int i; if (arr_size = 0; i--) if (arr != arr) System.out.printf("Phan tu lon thu 2: " + arr); 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 hợp của cách thức này: Time Complexity: O(n log n).

Duyệt mảng 2 lần

Phương pháp này chuyển động hiệu quả hơn phương pháp đầu tiên, bọn họ sẽ bắt buộc duyệt mảng 2 lần. Trong lượt đầu tiên chúng ta sẽ search ra bộ phận lớn nhất. Trong lượt duyệt sản phẩm công nghệ hai, họ lại tìm phần tử lớn nhất trong số phần tửcòn lại, các loại trừ phần tử lớn duy nhất trước đó.

public class Main { static void print2largest(int arr<>, int arr_size) int i, second; if (arr_size Output

Phan tu lon thu 2: 34Độ phức hợp của phương pháp này: Time Complexity: O(n).

Xem thêm: Thuật Toán Tìm Ước Chung Lớn Nhất Của 2 Số Nguyên Bằng C/C++

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

So với giải pháp trên thì đó là cách hiệu quả nhất vì chúng ta chỉ tốn 1 lần chú ý mảng. Trang bị tự xúc tiến sẽ như sau

1, Khởi tạo trở thành first = second = Integer.MIN_VALUE2, để ý mảng + Nếu phần tử hiện tại arr > first => second = first, first = arr + Nếu bộ phận hiện tại first second = arr3, trả về second thực hiện mã Java

public class Main static void print2largest(int arr<>, int arr_size) int i, first, second; if (arr_size first) second = first; first = arr; if (arr second) second = arr; 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 hợp của cách thức này: Time Complexity: O(n log n).