Tìm phần tử bị thiếu trong một mảng các số liên tiếp được sắp xếp trong C ++

Khái niệm

Đối với một mảng mảng đã cho [] gồm n số nguyên riêng biệt, các phần tử được xếp theo thứ tự tăng dần với một phần tử bị thiếu. Nhiệm vụ của chúng tôi là xác định phần tử còn thiếu.

Đầu vào

array[] = {1, 2, 3, 4, 5, 6, 7, 9}

Đầu ra

8

Đầu vào

array[] = {-4, -2, -1, 0, 1, 2}

Đầu ra

-3

Đầu vào

array[] = {1, 2, 3, 4}

Đầu ra

-1

Không có phần tử nào bị thiếu.

Phương pháp

Nguyên tắc

• Tìm kiếm sự không nhất quán:Theo nguyên tắc này, sự khác biệt giữa bất kỳ phần tử nào và chỉ mục của nó phải là mảng [0] cho mọi phần tử.

Ví dụ,

A [] ={1, 2, 3, 4, 5} -> Nhất quán

B [] ={201, 202, 203, 204} -> Nhất quán

C [] ={1, 2, 3, 5, 6} -> Không nhất quán là C [3] - 3! =C [0] tức là 5 - 3! =1

• Việc xác định sự không nhất quán giúp chỉ quét một nửa mảng mỗi lần trong O (logN).

Thuật toán

• Xác định yếu tố trung gian và xác minh xem nó có nhất quán hay không.

• Nếu phần tử giữa nhất quán, thì hãy xác minh xem sự khác biệt giữa phần tử giữa và phần tử tiếp theo có cao hơn 1 hay không, tức là xác minh nếu mảng [giữa + 1] - mảng [giữa]> 1

  • Nếu có, thì mảng [mid] + 1 là phần tử bị thiếu.

  • Nếu không, chúng ta phải quét nửa mảng bên phải từ phần tử ở giữa và chuyển sang bước 1.

• Nếu phần tử giữa không nhất quán, thì hãy xác minh xem sự khác biệt giữa phần tử giữa và phần tử trước của nó có cao hơn 1 không, tức là xác minh nếu mảng [giữa] - mảng [giữa - 1]> 1

  • Nếu có, thì mảng [mid] - 1 là phần tử bị thiếu.

  • Nếu không, chúng ta phải quét nửa mảng bên trái từ phần tử ở giữa và chuyển sang bước 1.

Ví dụ

// CPP implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// Shows function to return the missing element
int findMissing(int array[], int n1){
   int low = 0, high = n1 - 1;
   int mid1;
   while (high > low){
      mid1 = low + (high - low) / 2;
      // Verify if middle element is consistent
      if (array[mid1] - mid1 == array[0]){
         // Here, no inconsistency till middle elements
         // When missing element is just after
         // the middle element
         if (array[mid1 + 1] - array[mid1] > 1)
            return array[mid1] + 1;
         else{
            // Go right
            low = mid1 + 1;
         }
      }
      else{
         // Here inconsistency found
         // When missing element is just before
         // the middle element
         if (array[mid1] - array[mid1 - 1] > 1)
            return array[mid1] - 1;
         else{
            // Go left
            high = mid1 - 1;
         }
      }
   }
   // Here, no missing element found
   return -1;
}
// Driver code
int main(){
   int array[] = { -9, -8, -6, -5, -4, -3, -2, -1, 0 };
   int n1 = sizeof(array)/sizeof(array[0]);
   cout <<"The Missing Element:" <<(findMissing(array, n1));
}

Đầu ra

The Missing Element:-7