Tìm phần tử lớn thứ 2 trong mảng C
|
Show
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ếpBà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ầnPhươ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ầnSo 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ề secondTriể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). Would love your thoughts, please comment.x
Video giải thích chi tiết về Tìm phần tử nhỏ thứ hai trong mảng, Tìm phần tử lớn thứ hai trong mảng | Tự học lập trình C
#include "stdio.h"
#include "limits.h"
int a[100];
int n; void nhapMang(int x[100], int &n){ printf("Nhap vao so luong phan tu: "); scanf("%d", &n); for(int i=0; i
 Giải thuật với tên gọi "Find second largest number in an array" được mô tả như sau: 1) Initialize two variables first and second to INT_MIN as, first = second = INT_MIN 2) Start traversing the array, a) If the current element in array say arr[i] is greater than first. Then update first and second as, second = first first = arr[i] b) If the current element is in between first and second, then update second to store the value of current variable as second = arr[i] 3) Return the value stored in second. Ứng với mô tả trên, cài đặt bằng C của thuật toán sẽ tương tự như sau: #includeChú thích: - Tạo mảng động với n = 10 phần từ. - Giá trị của mỗi phần tử được sinh ngẫu nhiên trong khoảng từ 0 đến 200. - In ra phần tử lớn nhất và phần tử lớn thứ nhì, kết thúc chương trình. Kết quả sau khi chạy chương trình (Output): 151 99 178 126 31 36 70 129 117 159 max=178, second_max=159. Xin vui lòng chờ đợi Dữ liệu bài viết đang được tải về BÌNH LUẬN
Chương trình tìm giá trị lớn thứ hai của mảng là một chương trình C điển hình về mảng. Chương trình này giúp bạn hiểu cách sử dụng vòng lặp, mảng, lệnh IF và các toán tử điều kiện trong C. Để giải bài tập C này, chúng ta duyệt qua từng phần tử trong mảng và kiểm tra xem phần tử đó có phải là lớn thứ hai không. Chương trình CDưới đây là chương trình C để giải bài tập tìm giá trị lớn thứ hai của mảng trong C: #includeQuảng cáo Biên dịch chương trình C trên sẽ cho kết quả:
Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.
Các bạn có thể mua thêm khóa học JAVA CORE ONLINE VÀ ỨNG DỤNG cực hay, giúp các bạn vượt qua các dự án trên trường và đi thực tập Java. Khóa học có giá chỉ 300K, nhằm ưu đãi, tạo điều kiện cho sinh viên cho thể mua khóa học. Nội dung khóa học gồm 16 chuơng và 100 video cực hay, học trực tiếp tại https://www.udemy.com/tu-tin-di-lam-voi-kien-thuc-ve-java-core-toan-tap/ Bạn nào có nhu cầu mua, inbox trực tiếp a Tuyền, cựu sinh viên Bách Khoa K53, fb: https://www.facebook.com/tuyen.vietjack Follow facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.vietjack để tiếp tục theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile.... mới nhất của chúng tôi. bai-tap-mang-mot-chieu-trong-c.jsp |
