数据结构
网络
关系数据库管理系统 (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 次浏览
广告