LeetCode（Binary Search)268. Missing Number

左手的ㄟ右手 2023-09-25 23:08 28阅读 0赞

# 1.问题 #

Given an array nums containing n distinct numbers in the range \[0, n\], return the only number in the range that is missing from the array.

Example 1:

> Input: nums = \[3,0,1\]  
> Output: 2  
> Explanation: n = 3 since there are 3 numbers, so all numbers are in the range \[0,3\]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

> Input: nums = \[0,1\]  
> Output: 2  
> Explanation: n = 2 since there are 2 numbers, so all numbers are in the range \[0,2\]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

> Input: nums = \[9,6,4,2,3,5,7,0,1\]  
> Output: 8  
> Explanation: n = 9 since there are 9 numbers, so all numbers are in the range \[0,9\]. 8 is the missing number in the range since it does not appear in nums.

Constraints:

*  n == nums.length
 *  1 <= n <= 104
 *  0 <= nums\[i\] <= n  
    All the numbers of nums are unique.

# 2. 解题思路 #

## 方法1： ##

> 1.首先获取 nums 数组的长度 len。然后，使用 Arrays.sort() 方法对数组进行排序。  
> 2.接着，使用一个 while 循环来遍历数组。在循环中，使用 for 循环遍历数组中的每个元素。  
> 如果当前的 i 不等于当前的元素 n，那么 i 就是缺失的数字，直接返回 i。否则，继续循环，并将 i 加 1，直到找到缺失的数字。  
> 3.最后，如果数组中的所有数字都不缺失，那么 i 的值就等于数组的长度 len。此时，返回 i 即可。

## 方法2： ##

> 一种常见的思路是使用数学方法，求出 0~n 的所有数字的和，减去序列中所有数字的和，得到的差就是缺失的数字。这种方法可以在 O(n) 的时间内解决问题。  
> 1.首先，我们获取序列 nums 的长度 n。然后，我们计算 0~n 的所有数字的和 total\_sum，通过求和公式 total\_sum = n \* (n + 1) / 2 计算。  
> 2.接着，我们遍历 nums 数组，将 nums 数组中所有数字的和 sum 计算出来。  
> 3.最后，我们将 total\_sum 减去 sum，得到的差就是缺失的数字。

## 方法3： ##

> 1.首先，定义左指针 left 和右指针 right，并将 right 初始化为数组的长度 len。  
> 2.然后，使用 while 循环进行二分查找。在每次循环中，计算中间位置 mid，并根据数组下标和值的关系来判断缺失的数字在哪一边。  
> 3.如果 nums\[mid\] > mid，那么缺失的数字一定在 mid 的左边；  
> 4.如果 nums\[mid\] <= mid，那么缺失的数字一定在 mid 的右边。  
> 5.最后，返回左指针 left 的值，即为缺失的数字。

# 3. 代码 #

## 代码1： ##

class Solution {
        
        public int missingNumber(int[] nums) {
        
            int len = nums.length;
            // 对数组进行排序
            Arrays.sort(nums);
            int i = 0;
            // 遍历数组
            while (i <= len) {
        
                // 如果 i 不等于当前元素 n，那么 i 就是缺失的数字
                // 如果 i 等于当前元素 n，那么继续循环
                for (int n : nums) {
        
                    if (i != n) {
        
                        return i;
                    } else {
        
                        i++;
                    }
                }
            }
            return i;
        }
    }

## 代码2： ##

class Solution {
        
        public int missingNumber(int[] nums) {
        
            int n = nums.length;
            // 求出所有数的和
            int totalSum = n * (n + 1) / 2;
            // 减去nums中所有数的和，
            // 剩下的就是缺失的数字
            int sum = 0;
            for (int i = 0; i < n; i++) {
        
                sum += nums[i];
            }
            return totalSum - sum;
        }
    }

## 代码3： ##

public static int missingNumber(int[] nums) {
        
        int len = nums.length;
        // 对数组进行排序
        Arrays.sort(nums);
        // 定义左指针和右指针
        int left = 0, right = len;
        // 进行二分查找
        while (left < right) {
        
            int mid = (left + right) / 2;
            // 判断缺失的数字在哪一边
            if (nums[mid] > mid) {
        
                right = mid;
            } else {
        
                left = mid + 1;
            }
        }
        // 返回左指针的值，即为缺失的数字
        return left;
    }

> 解题思路是通过二分查找，寻找缺失的数字  
> 该方法首先使用 Arrays.sort() 方法对数组进行排序，然后使用二分查找的方法找到缺失的数字。在二分查找过程中，如果 i 在数组中不存在，那么 i 就是缺失的数字。  
> 该方法的时间复杂度为 O(nlogn)，因为要进行排序和二分查找，空间复杂度为 O(1)

class Solution {
        
        public int missingNumber(int[] nums) {
        
            int len = nums.length;
            // 对数组进行排序
            Arrays.sort(nums);
            int i = 0;
            // 使用二分查找的方法找到缺失的数字
            while (i <= len) {
        
                // 如果 i 在数组中不存在，那么 i 就是缺失的数字
                if (Arrays.binarySearch(nums, i) < 0) {
        
                    return i;
                } else {
        
                    i++;
                }
            }
            return i;
        }
    }