資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學在C++中查詢連續數字的有序陣列中缺失的元素
概念
對於給定的包含n個不同整數的陣列array[]，元素按升序順序排列，只有一個元素缺失。我們的任務是確定缺失的元素。
輸入
array[] = {1, 2, 3, 4, 5, 6, 7, 9}輸出
8
輸入
array[] = {-4, -2, -1, 0, 1, 2}輸出
-3
輸入
array[] = {1, 2, 3, 4}輸出
-1
沒有缺失的元素。
方法
原理
查詢不一致之處：根據此原理，任何元素與其索引之間的差值對於每個元素都必須為array[0]。
例如：
A[] = {1, 2, 3, 4, 5} -> 一致
B[] = {201, 202, 203, 204} -> 一致
C[] = {1, 2, 3, 5, 6} -> 不一致，因為C[3] – 3 != C[0]，即5 – 3 != 1
確定不一致之處有助於每次僅掃描陣列的一半，時間複雜度為O(logN)。
演算法
確定中間元素並驗證其是否一致。
如果中間元素一致，則驗證中間元素與其下一個元素之間的差值是否大於1，即驗證array[mid + 1] – array[mid] > 1。
如果是，則array[mid] + 1是缺失的元素。
否則，我們必須從中間元素掃描右半部分陣列，並跳轉到步驟1。
如果中間元素不一致，則驗證中間元素與其前一個元素之間的差值是否大於1，即驗證array[mid] – array[mid – 1] > 1。
如果是，則array[mid] – 1是缺失的元素。
否則，我們必須從中間元素掃描左半部分陣列，並跳轉到步驟1。
示例
// 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));
}輸出
The Missing Element:-7
更新於：2020年7月25日
346 次瀏覽
廣告