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