Giả sử chúng ta đã đưa ra một mảng các số nguyên chưa được sắp xếp có kích thước N. Nhiệm vụ là tìm phần tử max và max thứ hai riêng biệt có trong mảng. Mảng cũng có thể chứa các phần tử trùng lặp. Vì vậy, chúng ta chỉ phải tìm các phần tử riêng biệt. Ví dụ,
Đầu vào-1 -
N = 5
A[ ] = { 2, 2, 1, 3, 4 } Đầu ra -
4 3
Giải thích - Từ mảng đã cho, chúng ta có thể thấy ‘4’ là giá trị lớn nhất và ‘3’ là giá trị lớn nhất thứ hai.
Đầu vào-2 -
N = 4
A[ ] = { 1,3,3,2 } Đầu ra -
3 2
Giải thích - từ mảng có kích thước 4 đã cho, chúng ta có thể thấy ‘3’ là lớn nhất và ‘2’ là lớn thứ hai nên chúng ta sẽ trả về 3 2 dưới dạng đầu ra.
Phương pháp tiếp cận để giải quyết vấn đề này
Trong mảng kích thước N đã cho, cũng có thể có một số phần tử trùng lặp. Để tìm phần tử lớn nhất và lớn nhất thứ hai từ mảng, chúng ta có thể khởi tạo hai biến lưu trữ giá trị lớn nhất và giá trị lớn nhất thứ hai.
Ban đầu, nếu phần tử hiện tại lớn hơn giá trị tối đa thì chúng tôi sẽ lưu trữ giá trị của nó thành giá trị lớn nhất và giá trị của giá trị max (trước đó) thành giá trị tối đa thứ hai.
Để tìm phần tử khác biệt, chúng tôi sẽ kiểm tra xem phần tử hiện tại có bằng max hay không. Nếu giá trị hiện tại không bằng giá trị lớn nhất và cũng lớn hơn giá trị tối đa thứ hai, thì chúng tôi sẽ thay thế giá trị trước đó của giá trị tối đa thứ hai bằng giá trị hiện tại.
-
Khởi tạo và nhận đầu vào có kích thước N của mảng.
-
Một hàm maxAndSecondMax (int arr [], int size) nhận một mảng làm đầu vào và kích thước của mảng. Trả về phần tử tối đa và tối đa thứ hai của mảng đã cho.
-
Lặp lại các phần tử của mảng và tìm xem phần tử hiện tại có lớn hơn giá trị tối đa hay không, sau đó lưu trữ giá trị hiện tại thành giá trị lớn nhất và giá trị trước đó của giá trị lớn nhất với giá trị tối đa thứ hai.
-
Ngược lại, nếu giá trị hiện tại lớn hơn giá trị tối đa thứ hai, thì hãy thay thế giá trị trước đó bằng giá trị hiện tại. Ngoài ra, giá trị hiện tại không được bằng giá trị tối đa.
-
Kiểm tra xem giá trị tối đa thứ hai không chứa bất kỳ giá trị nào.
-
Trả về giá trị tối đa và giá trị tối đa thứ hai làm Đầu ra cuối cùng.
Ví dụ
#include<bits/stdc++.h>
using namespace std;
void maxAndSecondMax(int *arr, int size){
int max= INT_MIN;
int s_max= INT_MIN;
for(int i=0;i<size; ++i){
if(arr[i] >max){
s_max= max;
max= arr[i];
}
else if(arr[i]> s_max && arr[i]!= max){
s_max= arr[i];
}
}
if(s_max==INT_MIN){
s_max= -1;
}
cout<<max<<" "<<s_max;
}
int main(){
int N= 6;
int A[N]= {1,3,2,5,6,3};
maxAndSecondMax(A,N);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, thì nó sẽ in đầu ra là,
6 5
6 và 5 là các phần tử riêng biệt trong mảng có giá trị Tối đa và Tối đa thứ hai.