0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

输入: [0,1,3]
输出: 2

输入: [0,1,2,3,4,5,6,7,9]
输出: 8

特殊例子: 

输入: [0]
输出: 1

输入:[1]
输出: 0

最直接的思路就是按照数组遍历, 找出下标和值不对应的数字,  如果没有就是nums.count, 时间复杂度是O(N).

class Solution {
    func missingNumber(_ nums: [Int]) -> Int {

        for (i,num) in nums.enumerated() {
            if (i == num) {

            } else {
                return i
            }
        }
        return nums.count 
    }

}

优化下, 自然是用二分法了, 先找中间位置的数字, 

• 中间位置的数字 == 下表, 说明缺失的数字在后半部分, 并且不可能是此值, 所以用left = index+1
• 中间位置的数字 != 下表,  说明缺失的数字在前半部分, 同时也有可能是本身,所以index不能减1

最后还有2个特殊的值, 头部值和尾部值,

• 头部就判断是否等于0, 等于0, 说明正常;  不等于0, 那缺失的就是此数字
• 尾部判断是否等于count-1, 如果相等, 那就是缺了最后一个数字; 如果不相等, 说明缺失的数字在0~count-1之间

class Solution {
    func missingNumber(_ nums: [Int]) -> Int {
        let count = nums.count
        // 特殊用例, 如果最后一个都符合条件, 那就是count不满足
        if nums[count-1] == count-1 {
            return count
        }
        // 头部不满足条件,返回0
        if nums[0] != 0 {
            return 0
        }

        // 开始二分查找
        var left = 0
        var right = count-1
        while left<right {

            // 找到中间位置的数字
            let index = (left+right)/2
            // 中间位置数字相等,说明在后半部分,
            if index == nums[index] {
                left = index+1
            } else {
                // 中间位置数字不相等,说明在前半部分,也有可能是本身,所以index不能减1
                right = index
            }


        }

        return left

    }
}

最后

以上就是幸福饼干为你收集整理的0～n-1中缺失的数字的全部内容，希望文章能够帮你解决0～n-1中缺失的数字所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。