Tìm 3 phần tử lớn nhất trong mảng C++

Cho mảng arr[] gồm N phần tử không sắp xếp. Nhiệm vụ: tìm 3 phần tử lớn nhất.

Ví dụ minh họa

Input: arr[] = {7, 3, 9, 12, 1} Output: 12, 9, 7

Phương pháp 1: Duyệt một lần O(n)

Giữ 3 biến max, max2, max3. Cập nhật khi duyệt mảng.

#include <iostream> 
using namespace std; 

void findThreeLargestElements(int arr[], int arr_size){
    int max, max2, max3;
    max3 = max = max2 = arr[0];
    for(int i = 1; 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 << "Ba phần tử lớn nhất: " << max << ", " << max2 << ", " << max3;
}

int main(){
    int arr[] = {15, 2, 7, 86, 0, 21, 50};
    int n = sizeof(arr) / sizeof(arr[0]);
    findThreeLargestElements(arr, n);
    return 0;
}

Phương pháp 2: Sắp xếp O(n log n)

Sắp xếp giảm dần, lấy 3 phần tử đầu tiên phân biệt.

#include <bits/stdc++.h> 
using namespace std; 

void findThreeLargestElements(int arr[], int n){
    sort(arr, arr + n, greater<>());
    int j = 0;
    cout << "\nBa phần tử lớn nhất: ";
    for(int i = 0; i < n; i++){
        if(i == 0 || arr[i] != arr[i-1]){
            cout << arr[i] << " ";
            if(++j == 3) break;
        }
    }
}