寻找缺失的整数

[编程题]寻找缺失的整数

热度指数：372 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给你一个严格升序排列的正整数数组 arr 和一个整数 k 。

请你找到这个数组里第 k 个缺失的正整数。

示例1

输入

[2,3,4,7,11],5

输出

算法知识视频讲解

烟雨仔

这题有个测试案例有问题，通不过。明明说了是升序，还有个 42 34 44 。。。的，无语。

发表于 2021-02-09 18:32:21 回复(1)

AdamJensen

/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 获取缺失的正整数
* @param array int整型一维数组已知数组
* @param start int整型开始数
* @return int整型
*/
function getInter( nums , start ) {
// write code here
let missTotal = 0, n = nums.length

if(nums[0] !== 1){
let curRb = nums[0] - 1 + missTotal
if(curRb >= start){
return start
}
missTotal = curRb
}
for(let i = 1; i < n; ++i){
if(nums[i] - nums[i - 1] - 1 > 0){
let curRb = nums[i] - nums[i - 1] - 1 + missTotal
if(curRb >= start){
return nums[i - 1] + start - missTotal
}
else{
missTotal = curRb
}
}
}
return nums[n - 1] + start - missTotal
}
module.exports = {
getInter : getInter
};

发表于 2022-04-27 13:15:15 回复(0)

牛客589890733号

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 获取缺失的正整数
 * @param array int整型一维数组 已知数组
 * @param start int整型 开始数
 * @return int整型
 */
function getInter( array ,  start ) {
    let expectedValue = 1
    let count = 0
    for (let cur of array) {
        const miss = cur - expectedValue
        if (count + miss >= start) return expectedValue + start - count - 1
        expectedValue = cur + 1
        count += miss
    }
    return expectedValue + start - count - 1
}
module.exports = {
    getInter : getInter
};

发表于 2022-01-29 16:33:38 回复(0)

树枝在风中飘动

function getInter( array ,  start ) {
    var max = array[array.length - 1];
    var res, count = 0;
    for (var i = 1; i < max; i++) {
        if (array.indexOf(i) === -1) {
            count ++;
            if (count === start) {
                return i
            }
        }
    }
}

js是这样写的，12个测试用例通过了9个，是哪里还不完善么

发表于 2021-06-23 23:25:17 回复(0)

C/C++

楚渐灵丨

这个测试用例就离谱！

用例:
[42, 34, 44, 74, 141], 40

对应输出应该为:

40

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 获取缺失的正整数
     * @param array int整型一维数组 已知数组
     * @param arrayLen int array数组长度
     * @param start int整型 开始数
     * @return int整型
     */
    int getInter(int* array, int arrayLen, int start) {
        sort(array, array + arrayLen);
        int pos = start;
        if(array[0] != 1) {
            pos -= array[0] - 1;
        }
        // 如果缺少的第 k 个数都在 array[0]之前，那start 就是缺少的第 k 个数
        if(pos < 0) {
            return start;
        }
        for(int i = 1; i < arrayLen; i++) {
            while(array[i] > array[i-1] + 1) {
                pos--;
                array[i-1] += 1;
                if(pos == 0) {
                    return array[i-1];
                }
            }
        }
        if(pos > 0) {
            return array[arrayLen-1] + pos;
        }
        return -1;
        
    }
};

发表于 2021-03-15 15:28:26 回复(0)

Zero′

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 获取缺失的正整数
 * @param array int整型一维数组 已知数组
 * @param start int整型 开始数
 * @return int整型
 */
// 给的不是严格上升的数组，就预处理了不管了，然后就过了
// 
function getInter( arr ,  s ) {
    let f = new Array(arr[arr.length-1] + s + 1).fill(0)
    for(let i=1;i<arr.length;i++) {
        if(arr[i] < arr[i-1]) arr[i] = 0
    }
    for(let i=0;i<arr.length;i++) {
        if(arr[i] === 0) continue
        f[arr[i]] = 1
    }
    let n = 0
    for(let i=1;;i++) {
        if(f[i] == 0) n++
        if(n === s) return i
    }
}
module.exports = {
    getInter : getInter
};

发表于 2021-01-24 16:42:42 回复(0)

saka__

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 获取缺失的正整数
 * @param array int整型一维数组 已知数组
 * @param start int整型 开始数
 * @return int整型
 */
function getInter( array ,  start ) {
    // write code here
    var sum = 1;
    var arr = []; //缺失数的数组
    while(true){
        if(array[0] == sum){
            array.shift()
        }else{
           arr.push(sum)
        }
        if(arr.length == start){
            break;
        }
        sum++
    }
    return arr.pop()
}
module.exports = {
    getInter : getInter
};

发表于 2020-12-24 15:47:37 回复(0)

Mirko_996

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 获取缺失的正整数
# @param array int整型一维数组 已知数组
# @param start int整型 开始数
# @return int整型
#
class Solution:
    def getInter(self , array , start ):
        # write code here
        if not array: return start
        count = start
        pre = 0
        for v in array:
            if v <= pre:
                break
            if v - pre > count:
                break
            else:
                count = count - (v - pre - 1)
                pre = v
        return pre + count

发表于 2020-12-17 23:29:05 回复(0)