【LeetCode】268. 缺失数字（Java）

给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 … n 中没有出现在序列中的那个数。

这道题和剑指 Offer 53 - II. 0～n-1中缺失的数字很像，不同的是这道题是乱序，而剑指的是有序的，之前《【LeetCode】剑指 Offer 53 - II. 0～n-1中缺失的数字（Java）》的文章里用的是二分查找解决的，而这道题是乱序，如果想用二分查找，需要先对数组进行排序，而不想排序的话，二分查找就用不了了。

解法一

二分查找

class Solution { public int missingNumber(int[] nums) { //二分查找 Arrays.sort(nums); int left = 0, right = nums.length - 1; //这里相等是因为left和right可能都指向缺口的前一个，所以需要再循环一次，让left加1，指向正确的缺口 while (left <= right) { //取中间值 int mid = left + (right - left) / 2; //如果内容和下标一致，说明在右边 if (nums[mid] == mid) left = mid + 1; else right = mid - 1; } return left; } }

效率稍微差了些。

解法二

不排序，统计数字

class Solution { public int missingNumber(int[] nums) { //乱序，但是是从0到n，所以可以统计出现的数字 //因为nums缺失了一个数字，所以创建的数组要比原数组大一位 //不排序 int[] arr = new int[nums.length + 1]; for (int num : nums) { arr[num]++; } //遍历arr数组，内容为0就是缺失的数字 for (int i = 0; i < arr.length; i++) if (arr[i] == 0) return i; //没找到返回-1，不过这道题都是可以找到的 return -1; } }