Tìm Phần Tử Lớn Thứ 2 Trong Mảng

     

Bài toán: cho một mảng số nguyên, viết một công tác tìm ra số lớn thứ hai 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: thành phần lớn thứ hai là 34.Input: arr<> = 10, 5, 10Output: phần tử lớn thứ 2 là 5.Input: arr<> = 10, 10, 10Output: không tồn tại thành phần lớn thứ hai trong mảngĐây có lẽ rằng là bài bác toán có lẽ rằng nhiều bạn sinh viên sẽ gặp mặt phải trong quá trình học hoặc chất vấn xin việc. Trong nội dung bài viết này bọn họ sẽ cùng nhau tìm ra một vài cách giải cho câu hỏi này sử dụng ngôn ngữ Java.

Cách 1 – sắp đến xếp

Bài này biện pháp giải đơn giản nhất bạn cũng có thể làm kia là bố trí mảng giảm dần, kế tiếp lấy ra số lớn thứ 2 trong mảng. đề xuất lưu số số lớn thứ hai phải là số có giá trị khác so cùng với số lớn nhất nằm nghỉ ngơi vị trí đầu tiên của mảng đang được sắp đến 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).

Xem thêm: 41 Món Ăn Dành Cho Bà Bầu Ngon Đủ 4 Nhóm Dinh Dưỡng Tốt Cho Thai Nhi Khỏe Mạnh

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, bọn họ sẽ yêu cầu duyệt mảng 2 lần. Trong lần đầu tiên bọn họ sẽ tìm ra phần tử lớn nhất. Trong lượt duyệt trang bị hai, chúng ta lại tìm bộ phận lớn nhất trong những phần tửcòn lại, loại trừ thành phần 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 tạp của phương thức này: Time Complexity: O(n).

Xem thêm: Lạm Dụng Nấm Lim Đen Có Tác Dụng Gì, Lạm Dụng Nấm Lim Xanh Có Hại Sức Khỏe

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

So với bí quyết trên thì đây là cách kết quả nhất vì bọn họ chỉ tốn 1 lần coi ngó mảng. đồ vật tự thực thi sẽ như sau

1, Khởi tạo biến first = second = Integer.MIN_VALUE2, chuyên chú mảng + Nếu bộ phận hiện tại arr > first => second = first, first = arr + Nếu thành 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 phương thức này: Time Complexity: O(n log n).