LeetCode 0～n-1中缺失的數(shù)字 [簡單]
一個(gè)長度為n-1的遞增排序數(shù)組中的所有數(shù)字都是唯一的假夺，并且每個(gè)數(shù)字都在范圍0～n-1之內(nèi)日矫。在范圍0～n-1內(nèi)的n個(gè)數(shù)字中有且只有一個(gè)數(shù)字不在該數(shù)組中档痪，請找出這個(gè)數(shù)字字柠。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof
示例 1:
輸入: [0,1,3]
輸出: 2
示例 2:
輸入: [0,1,2,3,4,5,6,7,9]
輸出: 8
限制：
1 <= 數(shù)組長度 <= 10000
題目分析
解法1
因?yàn)殚L度為 n - 1,每個(gè)數(shù)據(jù)都是唯一的，而且每個(gè)數(shù)字都是在 0 - n -1 之間 而且只有一個(gè)不在此范圍中 可以迭代狡赐，根據(jù)數(shù)組下標(biāo)的特性 只要 nums[i] != i;則返回i 只能從小向大迭代
解法2
順序數(shù)組查找問題 解決思路就是二分法
代碼實(shí)現(xiàn)
public class MissingNumber {
public static void main(String[] args) {
int[] nums = {1, 2, 3};
System.out.println(missingNumber(nums));
}
public static int missingNumber1(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == mid) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
public static int missingNumber(int[] nums) {
if (nums.length == 1) {
return nums[0] == 0 ? 1 : 0;
}
int i;
for (i = 0; i < nums.length; i++) {
if (nums[i] != i) {
return i;
}
}
if (i == nums.length) {
return i;
}
return -1;
}
}
