Links

53-II.0~n-1中缺失的数字

一、 题目

一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。
示例 1:
输入: [0,1,3]
输出: 2
示例 2:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
限制:
1 <= 数组长度 <= 10000
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、 分析

2.1 下标匹配

本题为有序的数据,因此可以通过下标匹配来寻找缺失的数字
func missingNumber(_ nums: [Int]) -> Int {
var tmp = 0
for i in nums {
if tmp != i {
return tmp
}
else {
tmp += 1
}
}
return tmp
}

2.2 二分法

排序数组中的搜索问题,首先可以想到 二分法 解决,时间复杂度降低为了 O(logN)。
1
func missingNumber(_ nums: [Int]) -> Int {
var per = 0, aft = nums.count - 1
while per <= aft {
// 求中间下标
let m = (per + aft) / 2
if nums[m] == m {
per = m + 1
}
else {
aft = m - 1
}
}
return per
}