如何以较低的时间复杂度编写代码以查找给定数组范围内缺少的元素?

Question

我的函数应该返回给定数组范围内缺少的元素。 所以我首先对数组进行排序并检查 i 和 i+1 之间的差异是否不等于 1，我返回缺少的元素。

// Given an array A such that:
// A[0] = 2
// A[1] = 3
// A[2] = 1
// A[3] = 5
// the function should return 4, as it is the missing element.
function solution(A) {
A.sort((a,b) => {
return b<a;
})
var len = A.length;
var missing;
for( var i = 0; i< len; i++){
if( A[i+1] - A[i] >1){
missing = A[i]+1;
}
}
return missing;
}

我喜欢上面，但是如何更有效地编写它？

Answer 1

可以通过使用缺失值集来使用单循环方法。

在循环中，从缺失的集合中删除每个数字。

如果找到新的最小值，则所有缺失的数字都将添加到缺失数字集中，最小值除外，以及新的最大数字。

缺少的数字集在末尾包含结果。

function getMissing(array) {
var min = array[0],
max = array[0],
missing = new Set;

array.forEach(v => {
if (missing.delete(v)) return;                   // if value found for delete return
if (v < min) while (v < --min) missing.add(min); // add missing min values
if (v > max) while (v > ++max) missing.add(max); // add missing max values
});
return missing.values().next().value;                // take the first missing value
}
console.log(getMissing([2, 3, 1, 5]));
console.log(getMissing([2, 3, 1, 5, 4, 6, 7, 9, 10]));
console.log(getMissing([3, 4, 5, 6, 8]));

Answer 2

好吧，从问题(因为它应该返回一个数字(和所有现有解决方案(至少是示例(来看，列表似乎是唯一的。对于这种情况，我认为我们可以sum整个数组，然后减去这些数字之间的预期总和将生成输出。

N个自然数之和

1 + 2 + ....... + i + ... + n我们可以按n * (n+1) / 2进行评估

现在假设，在我们的数组中，最小值为i，最大值为n

所以要评估我们可以i + (i+1) + ..... + n

A = 1 + 2 + ..... + (i-1) + i + (i+1) + .... n(即n*(n+1)/2(

B = 1 + 2 + ..... + (i-1)和

C = A - B将给我们 (i + (i+1( + ... + n(的总和

现在，我们可以迭代数组一次并评估实际总和(假设D(，C - D将给我们缺失的数字。

让我们首先为每个步骤创建相同的内容(不是性能最佳的，但更具可读性(，然后我们将尝试在一次迭代中完成

let input1 = [2, 3, 1, 5],
input2 = [2, 3, 1, 5, 4, 6, 7, 9, 10],
input3 = [3, 4, 5, 6, 8];
let sumNatural = n => n * (n + 1) / 2;
function findMissing(array) {
let min = Math.min(...array),
max = Math.max(...array),
sum = array.reduce((a,b) => a+b),
expectedSum = sumNatural(max) - sumNatural(min - 1);
return expectedSum - sum;
}
console.log('Missing in Input1: ', findMissing(input1));
console.log('Missing in Input2: ', findMissing(input2));
console.log('Missing in Input3: ', findMissing(input3));

现在，让我们尝试在一次迭代中完成所有操作(因为我们对max、min和sum迭代了 3 次(

let input1 = [2, 3, 1, 5],
input2 = [2, 3, 1, 5, 4, 6, 7, 9, 10],
input3 = [3, 4, 5, 6, 8];
let sumNatural = n => n * (n + 1) / 2;
function findMissing(array) {
let min = array[0],
max = min,
sum = min,
expectedSum;
// assuming the array length will be minimum 2
// in order to have a missing number
for(let idx = 1;idx < array.length; idx++) {
let each = array[idx];
min = Math.min(each, min); // or each < min ? each : min;
max = Math.max(each, max); // or each > max ? each : max;
sum+=each; 
}
expectedSum = sumNatural(max) - sumNatural(min - 1);
return expectedSum - sum;
}
console.log('Missing in Input1: ', findMissing(input1));
console.log('Missing in Input2: ', findMissing(input2));
console.log('Missing in Input3: ', findMissing(input3));

Answer 3

sort您可以将每个值放入Set中，找到最小值，然后从最小值开始迭代，检查集合是否有有问题的数字，O(N)。(集有保证O(1)查找时间(

const input1 = [2, 3, 1, 5];
const input2 = [2, 3, 1, 5, 4, 6, 7, 9, 10];
const input3 = [3, 4, 5, 6, 8];
function findMissing(arr) {
const min = Math.min(...arr);
const set = new Set(arr);
return Array.from(
{ length: set.size },
(_, i) => i + min
).find(numToFind => !set.has(numToFind));
}
console.log(findMissing(input1));
console.log(findMissing(input2));
console.log(findMissing(input3));

Answer 4

如果数组items并且缺失和现有diff之间的差异为 1：

const missingItem = items => [Math.min(...items)].map(min => items.filter(x =>
items.indexOf(x-diff) === -1 && x !== min)[0]-diff)[0]

会给出O(n^2)的复杂性.

它翻译为：找到最小值并检查数组中的每个值 n 是否没有 n-diff 值成员，这也不是最小值。对于任何缺少大小差异的项目，它应该是正确的。

要查找 1 个以上的缺失元素，请执行以下操作：

([Math.min(...items)].map(min => items.filter(x =>
items.indexOf(x-diff) === -1 && x !== min))[0]).map(x => x-diff)

会给出O((m^2)(n^2))m是失踪成员的数量。

Answer 5

发现了这个老问题，想试一试。我有一个类似的想法 https://stackoverflow.com/users/2398764/koushik-chatterjee 因为我认为你可以通过知道总是只有一个缺失的元素来优化它。使用类似的方法但不使用最大值将导致以下结果：

function getMissing(arr) {
var sum = arr.reduce((a, b) => a + b, 0);
var lowest = Math.min(...arr);
var realSum = (arr.length) * (arr.length + 1) / 2 + lowest * arr.length;
return realSum - sum + lowest;
}

具有与上述相同的输入。我在几个浏览器上用jsperf运行它，它比其他答案更快。

https://jsperf.com/do-calculation-instead-of-adding-or-removing。

首先对所有内容求和，然后计算最低值，并计算整数的总和(如果恰好是最低的(。因此，例如，如果我们有2,3,4,5并想对它们求和，这与0,1,2,3求和然后添加最小的数字 + 在这种情况下的数字数量相同2 * 4因为(0+2),(1+2),(2+2),(3+2)将其变回原始数字。之后，我们可以计算差异，但随后必须再次将其增加最低值。为了抵消我们所做的转变。

Answer 6

你也可以使用while循环，如下所示 -

function getMissing(array) {
var tempMin = Math.min(...array);
var tempMax = tempMin + array.length;
var missingNumber = 0;

while(tempMin <= tempMax){
if(array.indexOf(tempMin) === -1) {
missingNumber = tempMin;
}
tempMin++;
}
return missingNumber;
}
console.log(getMissing([2, 3, 1, 5]));
console.log(getMissing([2, 3, 1, 5, 4, 6, 7, 9, 10]));
console.log(getMissing([3, 4, 5, 6, 8]));

Answer 7

我的方法基于对 O(N( 数组的就地排序，而不使用任何其他数据结构。

1. 在数组中找到 min 元素。
2. 就地排序。
3. 再次循环数组并检查是否有任何元素放错了位置，这就是答案！

function getMissing(ar) {
var mn = Math.min(...ar);
var size = ar.length;
for(let i=0;i<size;i++){
let cur = ar[i];
// this ensures each element is in its right place
while(cur != mn +i && (cur - mn < size) && cur != ar[cur- mn]) {
// swap
var tmp = cur; 
ar[i] = ar[cur-mn];
ar[cur-mn] = tmp;
}
}
for(let i=0; i<size; i++) {
if(ar[i] != i+mn) return i+mn;
}
}
console.log(getMissing([2, 3, 1, 5]));
console.log(getMissing([2, 3, 1, 5, 4, 6, 7, 9, 10]));
console.log(getMissing([3, 4, 5, 6, 8]));