刷题日记06-丢失的数据（排序）

丢失的数字

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1：

输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 2：

输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 3：

输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。

示例 4：

输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。

此题我共有三种解法，一种是我自己想出来的，还有两种是我看了题解。

方法一：先遍历0-n的每一个元素，拿得到的元素去输入数组中查询，利用Arrays.binarySearch()这个方法判断查询元素是否存在于数组中，如果不存在就把这个元素返回。要注意的是Arrays.binarySearch()这个方法在使用之前，要先把数组排序。代码如下：

class Solution {
    public int missingNumber(int[] nums) {
        int result = 0;
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i <= n; i++) {
            int binarySearch = Arrays.binarySearch(nums, i);
            if(binarySearch < 0){
                result = i;
            }
        }

        return result;
    }
}

方法二：把[0-n]当做一个数组，比如n = 3，数组为{0,1,2,3}。对输入的数组先进性排序，得到{0,1,3}。对输入数组{0,1,3}进行遍历，把遍历到的元素和[0-n]这个数组对应位置的元素进行比较，如果不相等就说明[0-n]对应位置的元素就是确实的元素。特殊情况就是确实的元素是尾元素，比如输入：nums = [0]，输出：1。在遍历的时候遍历不出来的，会完成遍历。也就是说如果完成了数组的遍历，就说明缺失的元素在尾部，尾部元素就等于缺失数组的长度n，将n在循环后返回即可。代码如下：

public static int missingNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        for (int i = 0; i < n; i++) {
            if (nums[i] != i){
                return i;
            }
        }

        return n;
    }

方法三：采用HashSet集合，将输入数组存入到Set集合中。遍历[0-n]，判断元素是否在集合中。代码如下：

class Solution {
    public static int missingNumber(int[] nums) {
        int n = nums.length;

        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }

        int missing = -1;

        for (int i = 0; i <= n; i++) {
            if (!set.contains(i)){
                missing = i;
            }
        }

        return missing;
    }
}