在两个排序数字之间查找缺失数字的最佳算法是什么？

Question

好的，这里有一个例子：

我们有一个阵列[1, 2, 3, 6, 7, 9, 15]

如果对其进行排序，我们需要找到两个数字之间的数字。它至少应该有助于在数组中创建一个由3个数字组成的序列。我们可以假设只有一个数字缺失。

在这种情况下，答案是8。我知道如何在python中使用in运算符强制执行，但效率不是很高。

def find_missing_number(arr):
for num in arr:
if (
num in arr and
num + 1 not in arr and
num + 2 in arr
):
return num + 1

欢迎使用任何语言解决方案。

Answer 1

这是C++17中的一个解决方案，

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
vector<int> v1 {1, 2, 3, 6, 7, 9, 15};
auto const it = std::adjacent_find(v1.begin(), v1.end(),
[] (auto const a, auto const b) {
return b - a == 2;
} );
if (it == v1.end()) {
std::cout << "no matchingn";
} else {
std::cout << "the missing number: " << 1 + *it << 'n';
}
}

Answer 2

查找距离为2的连续数字：

def find_missing_number(arr):
arr = sorted(arr)  # you'll only need this, if arr is not yet sorted
for a, b in zip(arr, arr[1:]):
if b - a == 2:
return a + 1

Answer 3

您可以通过使用一个集合来加快它。并删除毫无意义的num in arr检查(这总是正确的，因为您正在执行for num in arr(。

def find_missing_number(arr):
s = set(arr)
for num in arr:
if (num + 1 not in s) and (num + 2 in s):
return num + 1

Answer 4

我建议的逻辑是相同的。在这个例子中，对于num＝最小到最大最小＝1和最大＝15，

循环并查看循环和循环+2是否在阵列中，循环+1是否不在阵列中