Phần tử thiếu K-th trong mả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 đã sắp xếp cho trước.

Tìm số thứ K 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 đã sắp xếp.
• Khởi tạo hai biến difference và count = K.
• Duyệt mảng:
  • Nếu phần tử hiện tại khác phần tử tiếp theo:
    • Tìm hiệu hai số.
    • Nếu hiệu >= K, trả về phần tử hiện tại + count.
    • Ngược lại trừ hiệu từ count.
• Trả về -1.

Ví dụ

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

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

int findMissingNumber(int arr[], int k, int n) { 
    int difference, count = k; 
    for(int i = 0 ; i < n - 1; i++) { 
        if ((arr[i] + 1) != arr[i + 1]) { 
            difference = arr[i + 1] - arr[i] - 1; 
            if (difference >= count) { 
                return arr[i] + count; 
            } else { 
                count -= difference; 
            } 
        } 
    } 
    return -1; 
} 

int main() { 
    int arr[] = { 1, 2, 3, 5, 10 }, n = 5; 
    int k = 3; 
    cout << findMissingNumber(arr, k, n) << 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.