268. 缺失数字

我就是我 2023-03-12 09:02 51阅读 0赞

# 题目来源 #

[leetcode][]

[面试题 17.04. 消失的数字][17.04.]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

# 题目解析 #

## 解1：数学求和 ##

*  求出 0 到 n 之间所有的数字之和
 *  遍历数组计算出原始数组中数字的累积和
 *  两和相减，差值就是丢失的那个数字

public static int missingNumber(int[] nums) {
        
            int n = nums.length;
            int sum = (n)*(n+1)/2;
            for (int i = 0; i < n; i++){
        
                sum = sum - nums[i];
            }
            return sum;
        }

![在这里插入图片描述][2020051415222215.gif]ttps://mp.weixin.qq.com/s/WBXkHdm-Vm-Wwn5hsI9Ryw)

## 解2：异或 ##

和之前那道 [只出现一次的数字][Link 1] 很类似：

如果我们补充一个完整的数组和原数组进行组合，那所求解的问题就变成了 只出现一次的数字。

class Solution {
        
        public int missingNumber(int[] nums) {
        
            int i = 0;
            int sum = 0;
            for (i = 0; i <  nums.length; i++){
        
                sum = sum ^ nums[i] ^ i;
            }
            return sum ^ i;
        }
    }

![在这里插入图片描述][20200514153937643.png]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]

## 解3：排序查找 ##

将数组进行排序后，利用二分查找的方法来找到缺少的数字，注意搜索的范围为 0 到 n 。

> 注：由于一开始进行了排序操作，因此使用二分法的性能是不如上面两种方法。

public class Solution {
        
        public int missingNumber(int[] nums) {
        
            Arrays.sort(nums);
            int left = 0;
            int right = nums.length;
            while (left < right){
        
                int mid = (left + right) / 2;
                if (nums[mid] > mid){
        
                    right = mid;
                }else{
        
                    left = mid + 1;  
                }
            }
            return left;
        }
    }

参考：[https://mp.weixin.qq.com/s/WBXkHdm-Vm-Wwn5hsI9Ryw][https_mp.weixin.qq.com_s_WBXkHdm-Vm-Wwn5hsI9Ryw]

[leetcode]: https://leetcode-cn.com/problems/missing-number/
[17.04.]: https://blog.csdn.net/zhizhengguan/article/details/105679990
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: /images/20230312/b1d63fd42ff04fe09fd30b257dfde99b.png
[2020051415222215.gif]: /images/20230312/f21982e2c0da44759cb2221a06c7e9f4.png
[Link 1]: https://blog.csdn.net/zhizhengguan/article/details/106119763
[20200514153937643.png]: /images/20230312/54beddc6bd80477891db971472a85085.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]: /images/20230312/087a59f196a247ac99d3ad14dd4d059d.png
[https_mp.weixin.qq.com_s_WBXkHdm-Vm-Wwn5hsI9Ryw]: https://mp.weixin.qq.com/s/WBXkHdm-Vm-Wwn5hsI9Ryw