Phần tử thiếu K-th trong mảng không sắp xếp trong C++

Trong hướng dẫn này, chúng ta sẽ viết một chương trình tìm phần tử thiếu thứ K trong mảng không sắp xếp cho trước.

Tìm K-th số bị thiếu từ min đến max trong mảng không sắp xếp. Hãy xem các bước giải quyết.

• Khởi tạo mảng không sắp xếp.
• Chèn tất cả phần tử vào set.
• Tìm max và min từ mảng.
• Viết vòng lặp từ min đến max, duy trì biến đếm:
  • Nếu phần tử hiện tại không có trong set, tăng count.
  • Nếu count = K, trả về i.

Ví dụ

Dưới đây là mã nguồn C++:

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

int findMissingNumber(int arr[], int n, int k) { 
    unordered_set<int> numbers; 
    int count = 0; 
    for (int i = 0; i < n; i++) { 
        numbers.insert(arr[i]); 
    } 
    int max = *max_element(arr, arr + n); 
    int min = *min_element(arr, arr + n); 
    for (int i = min + 1; i < max; i++) { 
        if (numbers.find(i) == numbers.end()) { 
            count++; 
        } 
        if (count == k) { 
            return i; 
        } 
    } 
    return -1; 
} 

int main() { 
    int arr[] = { 1, 10, 3, 2, 5 }, n = 5; 
    int k = 3; 
    cout << findMissingNumber(arr, n, k) << endl; 
    return 0; 
}

Kết quả

Nếu bạn chạy mã trên, kết quả sẽ là:

7

Kết luận

Nếu bạn có bất kỳ thắc mắc nào về hướng dẫn này, hãy để lại bình luận bên dưới.