Trong bài toán này, chúng ta được đưa ra một arr [] bao gồm N phần tử không được sắp xếp. Nhiệm vụ của chúng tôi là tìm ba phần tử lớn nhất trong một mảng .
Hãy lấy một ví dụ để hiểu vấn đề,
Input : arr[] = {7, 3, 9, 12, 1}
Output : 12, 9, 7 Phương pháp tiếp cận giải pháp
Về cơ bản, chúng ta cần tìm ba phần tử lớn nhất của mảng và in chúng. Điều này có thể được thực hiện theo nhiều cách,
Phương pháp 1
Đối với ba phần tử lớn nhất, chúng tôi sẽ tạo ba phần tử giữ giá trị của chúng, max, max2 và max3 và đặt các giá trị này thành arr [0].
Sau đó, chúng ta sẽ lặp từ dạng i -> 1 đến n-1 và cho từng phần tử
if (arr [i]> max) -> max3 =max2, max2 =max, max =arr [i].
else if (arr [i]> max2) -> max3 =max2, max2 =arr [i].
else if (arr [i]> max3) -> max3 =arr [i].
Ở cuối vòng lặp, chúng tôi sẽ in cả ba giá trị.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#include <iostream>
using namespace std;
void findThreeLargestElements(int arr[], int arr_size){
int max, max2, max3;
max3 = max = max2 = arr[0];
for(int i = 0; i < arr_size; i++){
if (arr[i] > max){
max3 = max2;
max2 = max;
max = arr[i];
}
else if (arr[i] > max2){
max3 = max2;
max2 = arr[i];
}
else if (arr[i] > max3)
max3 = arr[i];
}
cout<<endl<<"Three largest elements of the array are "<<max<<", "<<max2<<", "<<max3;
}
int main(){
int arr[] = {15, 2, 7, 86, 0, 21, 50};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The array is : ";
for(int i = 0; i < n; i++)
cout<<arr[i]<<"\t";
findThreeLargestElements(arr, n);
return 0;
} Đầu ra
The array is : 15 2 7 86 0 21 50 Three largest elements of the array are 86, 50, 21
Phương pháp 2
Một phương pháp khác để giải quyết vấn đề là sắp xếp mảng và sau đó in ba phần tử đầu tiên của mảng là ba phần tử lớn nhất.
Thuật toán
Bước 1 - sắp xếp mảng bằng kỹ thuật sắp xếp.
Bước 2 - in ba phần tử đầu tiên:arr [0], arr [1], arr [2]
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#include <bits/stdc++.h>
using namespace std;
void findThreeLargestElements(int arr[], int n){
sort(arr, arr + n, std::greater<>());
int j = 0;
cout<<"\nThree largest elements are ";
for(int i = 0; i < n; i++){
if(arr[i] != arr[i+1]){
cout<<arr[i]<<" ";
j++;
}
if(j == 3){
break;
}
}
}
int main(){
int arr[] = {15, 2, 7, 86, 0, 21, 50, 53, 50};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The array is : ";
for(int i = 0; i < n; i++)
cout<<arr[i]<<"\t";
findThreeLargestElements(arr, n);
return 0;
} Đầu ra
The array is : 15 2 7 86 0 21 50 53 50 Three largest elements are 86 53 50