ค่า K สูงสุดที่อาร์เรย์มีอย่างน้อย K สมาชิกที่ >= K ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr ภารกิจคือการสร้างโปรแกรมหาค่า K สูงสุดที่อาร์เรย์มีอย่างน้อย K สมาชิกที่มากกว่าหรือเท่ากับ K ใน C++

คำอธิบายปัญหา

เราต้องหาค่า K ที่ทำให้มีสมาชิกในอาร์เรย์ที่มากกว่าหรือเท่ากับ K อย่างน้อย K ตัว

ตัวอย่างเพื่อเข้าใจปัญหา:

อินพุต: arr[] = {3, 5, 1, 7, 6, 6, 4, 8}

เอาต์พุต: 5

คำอธิบาย

สมาชิกในอาร์เรย์ที่มากกว่าหรือเท่ากับ 5: 5, 6, 6, 7, 8 (มี 5 ตัว)

แนวทางแก้ปัญหา

วิธีแก้ที่เรียบง่ายและมีประสิทธิภาพคือการเรียงลำดับอาร์เรย์ และตรวจสอบจาก index สุดท้ายว่าจำนวนสมาชิกหลังจากสมาชิกนั้นมากกว่าค่าของสมาชิกนั้นหรือไม่ ถ้าใช่ ให้คืนค่าสมาชิกนั้น

ตัวอย่างโค้ด

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

int CalcMaximumVal(int arr[], int N) {
    sort(arr, arr + N);
    for (int i = (N - 1); i >= 0; i--) {
        if (arr[i] <= (N - i))
            return arr[i];
    }
}

int main() {
    int arr[] = {4, 7, 2, 3, 8};
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << "The maximum value K such that array has at-least K elements that are >= K is " << CalcMaximumVal(arr, N);
    return 0;
}

ผลลัพธ์

The maximum value K such that array has at-least K elements that are >= K is 3