面试题53 - II. 0～n-1中缺失的数字

ゝ一纸荒年。 2023-02-15 15:54 12阅读 0赞

# 1. 数组有序： #

## 题目： ##

[面试题53 - II. 0～n-1中缺失的数字][53 - II. 0_n-1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]

## 题解： ##

### 1. 题解一：二分法 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]

### 2. 题解二：顺序扫描 ###

一趟扫描，若nums\[i\] != i，表示该元素值缺失，返回其下边即可；若一直到数组的最后一个元素都是nums\[i\] == i，表示缺失的元素正好就是nums\[nums.length\]，因此，返回其对应的下标即可。

## 代码： ##

### 1. 代码一：二分法 ###

public class 面试题53_2 { 
    
        // 方法1：
        public static int missingNumber(int[] nums) { 
            int i = 0;
            int j = nums.length - 1;
            while(i <= j)
            { 
                int mid = (i + j) / 2;
                if(nums[mid] == mid)
                { 
                    i = mid + 1;
                }
                else if (nums[mid] != mid)
                { 
                    j = mid - 1;
                }
            }
            return i;
        }
    
        public static void main(String[] args) { 
            int nums[] = {  0, 1, 2, 3, 4, 5, 6, 7, 9 };
            int res = missingNumber(nums);
            System.out.println(res);
        }
    }

### 2. 代码二：顺序扫描 ###

// 方法2：
    public static int missingNumber(int[] nums) { 
        for(int i = 0; i < nums.length; i++)
        { 
            if(nums[i] != i)
            { 
                return i;
            }
        }
        return nums.length;
    }

## 参考： ##

1.  [面试题53 - II. 0～n-1 中缺失的数字（二分法，清晰图解）][53 - II. 0_n-1 1]

# 2. 数组无序： #

## 题目： ##

**找1到n中缺失的数字（给定一个长度为n-1的整形数组，数字的范围在1到n（无重复），其中有一个缺失的数字）**

例如：给定一数组如 [1, 2, 6, 3, 4]，如何查找出缺失的数字 5.

## 题解： ##

### 1. 题解一：求和法 ###

解题思路：
    
    数字有规律，1~100 内的连续数字，只缺失一个数字，只要求和相减即可 (Sum1 - Sum2)。
    其中， Sum1 代表的是完整不缺数字的期待总和，等于 1+2+3+4+5+6=6*(6+1)/2=21，其演变表达式为 N(N+1)/2；
    Sum2 代表是的实际数组元素的总和，等于 1+2+6+3+4=16。所以缺失的数字为 5=21-16。
    时间复杂度：O(n) 空间复杂度：O(1)。但n过大时，求和存在溢出问题。
    // 用1+2+…+n减去当前输入数据的总和，则所得的差就是缺失的那个数。
    // n：最大元素的值而不是元素的个数

### 2. 题解二：异或法 ###

解题思路：
    
    利用异或运算，
    任何数异或自己都等于0，x ^ x = 0，任何数异或0都等于他自己 x ^ 0 = x；
    假如缺的为3。第一次异或后，result = 1 ^ 2 ^ 4 ^ 5 ^ N；
    第二次异或后，result = (1 ^ 2 ^ 4 ^ 5 ^ N) ^ (1 ^ 2 ^ 3 ^ 4 ^ 5 ^ N) = 0 ^ 3 = 3；
    时间复杂度：O(n) 空间复杂度：O(1)
    //异或方法，N：最大元素的值

### 3. 题解三：hash方法 ###

解题思路：
    
    对输入数据进行Hash，然后从头到尾遍历一次。
    时间复杂度O(n) 空间复杂度O(n)

## 代码： ##

### 1. 代码一：求和法 ###

public class 面试题53_2 { 
    
        // 方法3：
        // n：最大元素的值而不是元素的个数
        public static int missingNumber2(int[] nums, int n) { 
            int sum = n * (n + 1) / 2;
            for(int i = 0; i < nums.length; i++)
            { 
                sum = sum - nums[i];
            }
            return sum;
        }
    
        public static void main(String[] args) { 
            int nums2[] = {  1, 2, 6, 3, 4 };
            int res2 = missingNumber2(nums2, 6);
            System.out.println(res2);
        }
    }

### 2. 代码二：异或法 ###

public class 面试题53_2 { 
    
        // 方法4：
        // 异或方法，n：最大元素的值
        public static int missingNumber2(int[] nums, int n) { 
            int res = 0;
            // 最大值为n，缺失一个元素，则元素个数为n-1，元素下标为n-2
            // 第一次异或：
            for(int i = 0; i < n - 1; i++)
            { 
                res = res ^ nums[i];
            }
            // 第二次异或：
            for(int i = 1; i <= n; i++)
            { 
                res = res ^ i;
            }
            return res;
        }
    
        public static void main(String[] args) { 
            int nums2[] = {  1, 2, 6, 3, 4 };
            int res2 = missingNumber2(nums2, 6);
            System.out.println(res2);
        }
    }

### 3. 代码三：hash方法 ###

import java.util.*;
    
    public class 面试题53_2 { 
    
        // 方法5：
        // hash方法，n：最大元素的值
        // 在java中，Map集合中只能保存一个相同的key，如果再添加相同的key，则之后添加的key的值会覆盖之前key对应的值，Map中一个key只存在唯一的值。
        public static int missingNumber2(int[] nums, int n) { 
            int res = 0;
            HashMap<Integer, Integer> map = new HashMap<>();
            // HashMap 的长度比 n 大1
            // HashMap 的值从1开始，因此 HashMap 的 0 位不用
            for(int i = 1; i <= n; i++)
            { 
                map.put(i, 0);
            }
            // 最大值为n，缺失一个元素，则元素个数为n-1，元素下标为n-2
            for(int i = 0; i < n - 1; i++)
            { 
                map.put(nums[i], 1);
            }        
            for(int i = 1; i <= n; i++)
            { 
                if(map.get(i) == 0)
                { 
                    res = i;
                }
            }
            return res;
        }
    
        public static void main(String[] args) { 
            int nums2[] = {  1, 2, 6, 3, 4 };
            int res2 = missingNumber2(nums2, 6);
            System.out.println(res2);
        }
    }

## 参考： ##

1.  [找1到n中缺失的数字（长度为n-1的整形数组，数字的范围在1到n，找其中一个缺失的数字）][1_n_n-1_1_n]
2.  [面试涉及到的一些算法题][Link 1]
3.  [数组：找1到n中缺失的数字（长度为n-1的整形数组，数字的范围在1到n，找其中一个缺失的数字）][1_n_n-1_1_n 1]
4.  [在数组中查找缺失数字的最快方法][Link 2]
5.  [java HashMap插入重复Key值问题][java HashMap_Key]
6.  [java map中相同的key保存多个value值详解][java map_key_value]

[53 - II. 0_n-1]: https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200606125526921.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200606125654445.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200606125706333.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200606125743112.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200606125817719.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[53 - II. 0_n-1 1]: https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/solution/mian-shi-ti-53-ii-0n-1zhong-que-shi-de-shu-zi-er-f/
[1_n_n-1_1_n]: https://blog.csdn.net/qq_24336773/article/details/81709343
[Link 1]: https://xiaorui2.github.io/2019/07/27/%E9%9D%A2%E8%AF%95%E6%B6%89%E5%8F%8A%E5%88%B0%E7%9A%84%E4%B8%80%E4%BA%9B%E7%AE%97%E6%B3%95%E9%A2%98/
[1_n_n-1_1_n 1]: https://blog.csdn.net/qq_37933895/article/details/98788061
[Link 2]: https://www.it-swarm.dev/zh/java/%E5%9C%A8%E6%95%B0%E7%BB%84%E4%B8%AD%E6%9F%A5%E6%89%BE%E7%BC%BA%E5%A4%B1%E6%95%B0%E5%AD%97%E7%9A%84%E6%9C%80%E5%BF%AB%E6%96%B9%E6%B3%95/968274859/
[java HashMap_Key]: https://blog.csdn.net/intersting/article/details/72627353
[java map_key_value]: https://blog.csdn.net/weixin_37774620/article/details/79128212