Đếm phần tử có đúng X phần tử lớn hơn hoặc bằng X trong C++

Chúng ta được cho một mảng số nguyên. Mục tiêu là tìm số phần tử trong mảng thỏa mãn điều kiện:

Với mỗi phần tử, số lượng số lớn hơn hoặc bằng nó trong mảng phải chính xác bằng chính nó. Loại trừ chính phần tử đó. Nếu phần tử là X thì mảng có đúng X số lớn hơn hoặc bằng X. (Loại trừ phần tử đó).

Ví dụ

Đầu vào

Arr[] = { 0, 1, 2, 3, 4, 9, 8 }

Đầu ra

Phần tử đúng lớn hơn bằng chính nó: 1

Giải thích − Phần tử và số >= nó:

Arr[0]: 6 phần tử >= 0, 6 != 0 count=0
Arr[1]: 5 phần tử >= 1, 5 != 1 count=0
Arr[2]: 4 phần tử >= 2, 4 != 2 count=0
Arr[3]: 3 phần tử >= 3, 3 == 3 count=1
Arr[4]: 2 phần tử >= 4, 2 != 4 count=1
Arr[4]: 0 phần tử >= 9, 0 != 9 count=1
Arr[6]: 1 phần tử >= 8, 1 != 8 count=1

3 là phần tử duy nhất sao cho đúng 3 phần tử >= nó (4, 8, 9).

Đầu vào

Arr[] = { 1, 1, 1, 1, 1 }

Đầu ra

Phần tử đúng lớn hơn bằng chính nó: 0

Giải thích − Tất cả phần tử bằng nhau và count != 1.

Phương pháp sử dụng trong chương trình dưới đây

• Mảng số nguyên Arr[] lưu số nguyên.
• Số nguyên 'n' lưu độ dài mảng.
• Hàm findcount(int arr[], int n) nhận mảng và kích thước, trả về số lượng số như X giải thích trước.
• Biến count lưu số lượng số như X.
• Khởi tạo ans = 0, sẽ đếm các số như vậy.
• Duyệt mảng từ phần tử đầu (chỉ số 0) dùng vòng for.
• Trong vòng for duyệt từ đầu lại, nếu arr[j] >= arr[i] và i != j, tăng count.
• Sau vòng j, so sánh count với arr[i]. Nếu count == arr[i] (chính xác arr[i] phần tử >= arr[i]), tăng 'ans'.
• Sau cả hai vòng for trả về kết quả trong 'ans'.

Ví dụ mã nguồn

#include <iostream> 
#include <algorithm> 
using namespace std; 

int findcount(int arr[], int n) { 
    sort(arr, arr + n); 
    int count = 0; 
    int ans = 0; 
    for (int i = 0; i < n; i++) { 
        count = 0; 
        for (int j = 0; j < n; j++) { 
            if (arr[j] >= arr[i] && i != j) 
                count++; 
        } 
        if (count == arr[i]) 
            ans++; 
    } 
    return ans; 
} 

int main() { 
    int Arr[] = { 0, 1, 2, 3, 4, 5, 6 }; 
    int k = 7; 
    int n = sizeof(Arr) / sizeof(Arr[0]); 
    std::cout << "Phần tử đúng lớn hơn bằng chính nó: " << findcount(Arr, n); 
    return 0; 
}

Kết quả

Phần tử đúng lớn hơn bằng chính nó: 1