这道算法题太太太太太简单啦

淩亂°似流年 2022-01-30 04:41 209阅读 0赞

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

今天分享一道很简单的算法题。

题目来源于 LeetCode 上第 268 号问题：缺失数字。题目难度为 Easy，目前通过率为 50.2% 。

## 题目描述 ##

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

**说明：**

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

![640?wx\_fmt=png][640_wx_fmt_png]

## 题目解析 ##

这道题目有三种解法。

### 解法一：异或法 ###

和之前那道 **只出现一次的数字** 很类似：

> 只出现一次的数字: 给定一个**非空**整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

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

将少了一个数的数组与 0 到 n 之间完整的那个数组进行异或处理，因为相同的数字异或会变为了 0 ，那么全部数字异或后，剩下的就是少了的那个数字。

![640?wx\_fmt=png][640_wx_fmt_png 1]

#### 代码实现1 ####

class Solution {    public int missingNumber(int[] nums) {        int res = 0, i = 0 ;        //注意数组越界情况        for ( i = 0; i < nums.length;i++){            // i 表示完整数组中的数字，与原数组中的数字 nums[i] 进行异或，再与保存的结果异或            res = res^i^nums[i];        }        //最后需要与循环中无法使用到的那个最大的数异或        return res^i;    }}
        public int missingNumber(int[] nums) {
        
            int res = 0, i = 0 ;
            //注意数组越界情况
            for ( i = 0; i < nums.length;i++){
        
                // i 表示完整数组中的数字，与原数组中的数字 nums[i] 进行异或，再与保存的结果异或
                res = res^i^nums[i];
            }
            //最后需要与循环中无法使用到的那个最大的数异或
            return res^i;
        }
    }

#### 代码实现2 ####

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

### 解法二：求和法 ###

![640?wx\_fmt=gif][640_wx_fmt_gif]

//小吴之前担心会数据溢出，不过估计这题考察的不是这个，所以测试用例没写这种吧，还是能 AC 的class Solution {   public int missingNumber(int[] nums) {        int n = nums.length;        int sum = (n+0)*(n+1)/2;        for (int i=0; i<n; i++){            sum -= nums[i];        }        return sum; }}
    class Solution {
        
       public int missingNumber(int[] nums) {
        
            int n = nums.length;
            int sum = (n+0)*(n+1)/2;
            for (int i=0; i<n; i++){
        
                sum -= nums[i];
            }
            return sum;
     }
    }

### 解法三：二分法 ###

将数组进行排序后，利用二分查找的方法来找到缺少的数字，注意搜索的范围为 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;    }}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;
        }
    }

**END**

![640?wx\_fmt=png][640_wx_fmt_png 2]

**推荐阅读**：

*  [浅谈什么是动态规划以及相关的「股票」算法题][Link 1]

*  [面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

*  [如何有效的写算法题][Link 2]

*  [几道 BAT 算法面试中经常问的「字符串」问题][BAT]

*  [链表算法面试问题？看我就够了！][Link 3]

![640?wx\_fmt=png][640_wx_fmt_png 2]

欢迎长按下图关注公众号**五分钟学算法**，一起学习交流。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

**来和程序员小吴一起学算法**

![640?wx\_fmt=gif][640_wx_fmt_gif 1]

我就知道你在看！

[640_wx_fmt_jpeg]: /images/20220130/d406fffd6242421daa969d6f1fcab6cf.png
[640_wx_fmt_png]: /images/20220130/f07c0d11e4284e6fa565a778c974352b.png
[640_wx_fmt_png 1]: /images/20220130/b57d885451454f2bba9b583e819e41bb.png
[640_wx_fmt_gif]: /images/20220130/03a747b65e774849b57d0811f8993e5e.png
[640_wx_fmt_png 2]: /images/20220130/022e2e7190ec497aad8452283197d99e.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485288&idx=1&sn=fd043fc723f38bcaecc90d9945981f8a&chksm=fa0e68e9cd79e1ffd965205bb06b1731539bf2e0bbc5991664f5d1d9721b346ec08c85bb9042&scene=21#wechat_redirect
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485214&idx=1&sn=00de6e810caa7e261b8f2e19c3acd9cd&chksm=fa0e689fcd79e189282babbe3a688158b505e7b907971eede501addac9e0bec1e9d1c77ffb78&scene=21#wechat_redirect
[BAT]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485091&idx=1&sn=1503058d7c1313552f84073b495c5e76&chksm=fa0e6922cd79e034471194c636e89aa124941a13dabdf4d6197669f51d146f27098b124e5dd8&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484830&idx=1&sn=9d24fc787da4b49b82ac01c7f8de257b&chksm=fa0e6a1fcd79e309a2e7f3e09ec9913a55f1c077287c907f13528578b7785831a2effb3104e0&scene=21#wechat_redirect
[640_wx_fmt_jpeg 1]: /images/20220130/8ef7bb12b4bf4f6cb8ac6f654c95af28.png
[640_wx_fmt_gif 1]: /images/20220130/b063dca93eb54fdba57513d84d6d9b8c.png