phần tử bị thiếu thứ k 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 ra phần tử còn thiếu thứ k trong mảng đã sắp xếp.

Tìm số thứ k bị thiếu từ min đến max trong mảng chưa sắp xếp đã cho. Hãy xem các bước để giải quyết vấn đề.

• Khởi tạo mảng đã sắp xếp.
• Khởi tạo hiệu số hai biến và đếm với k.
• Lặp lại trên mảng.
  • Nếu phần tử hiện tại không bằng phần tử tiếp theo.
    • Tìm sự khác biệt giữa hai số.
    • Nếu sự khác biệt lớn hơn hoặc bằng k, thì trả về phần tử hiện tại cộng với số lượng.
    • Số khác trừ đi số chênh lệch.
• Trả về -1.

Ví dụ

Hãy xem mã.

#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;
}

Đầu ra

Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.

7

Kết luận

Nếu bạn có bất kỳ câu hỏi nào trong hướng dẫn, hãy đề cập đến chúng trong phần bình luận.