[js] 第249天 从一个无序的整数数组中，找出最小和最大数之间缺失的数字，要求最小的时间复杂度

[haizhilin2013]

第249天 从一个无序的整数数组中，找出最小和最大数之间缺失的数字，要求最小的时间复杂度

我也要出题

[NicholasBaiYa]

const findNum = function(arr) {
    let newArr = new Array()
    let maxNum = Math.max(...arr)
    let minNum = Math.min(...arr)
    for(let i = minNum; i < maxNum; i++){
        if(!arr.find(e => e == i)){
            newArr.push(i)
        }
    }
    return newArr
}

[xiaoqiangz]

function getArr(arr) {
let find = []
let min = Math.min(...arr)
let max = Math.max(...arr)
for(let i = min; i < max; i++) {
let num = arr[i]
if (!find.includes(num)) {
find.push(num)
}
}
return find
}

[Wyt-GitHub8000]

可以使用线性扫描来找出最小和最大数之间缺失的数字，并且时间复杂度为 O(n)，其中 n 为数组中元素的个数。

具体的做法如下：

首先找到数组中的最小值和最大值。

创建一个长度为最大值和最小值之间差值加1的布尔类型数组，用来记录每个数字是否出现过。

遍历原始数组，将出现过的数字在布尔类型数组中标记为 true。

遍历布尔类型数组，找到第一个为 false 的位置，即为最小和最大数之间缺失的数字。

以下是 JavaScript 的实现示例代码：

function findMissingNumber(nums) {
if (!nums || !nums.length) {
return null;
}
const minNum = Math.min(...nums);
const maxNum = Math.max(...nums);
const arr = new Array(maxNum - minNum + 1).fill(false);
for (let i = 0; i < nums.length; i++) {
arr[nums[i] - minNum] = true;
}
for (let i = 0; i < arr.length; i++) {
if (!arr[i]) {
return i + minNum;
}
}
return null;
}
该函数的时间复杂度为 O(n)，其中 n 为数组中元素的个数。

[ferrinweb]

const findHideNumbers = numbers => {
    const state = {}
    for(const number of numbers) state[number] = true
    const sortedNumber = Object.keys(state)
    const min = sortedNumber[0]
    const max = sortedNumber.pop()
    const hideNumbers = []
    for (let i = min; i < max; i++) {
        if (!state[i]) hideNumbers.push(i)
    }
    return hideNumbers
}
findHideNumbers([2,1,7,5,3,10]) // output: [4, 6, 8, 9]