【每日一道LeetCode】——面试题 17.04. 消失的数字、189. 轮转数组

水深无声 2024-04-07 14:02 40阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：月亮嚼成星~
> 
> 博客主页：[月亮嚼成星~的博客主页][Link 1]
> 
> 专栏：[每日一道LeetCode][LeetCode]
> 
> 工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
> 
> [点击免费注册和我一起刷题吧][Link 2]

**目录**

原题：

解题思路一：（排序找不同）

代码实现：

解题思路二：（数字加减法）

代码实现：

解题思路三：（异或法）

代码实现：

原题：

解题思路： （翻转法）

代码实现：

--------------------

## 原题： ##

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

数组`nums`包含从`0`到`n`的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？

**注意：**本题相对书上原题稍作改动

## ![cafdf39278aa4b2e833a9738f65182a3.png][]解题思路一：（排序找不同） ##

数组`nums`包含从`0`到`n`的所有整数，缺失的就在其中，所以我们可以进行排序，使数组的下标与数字对应，所以我们需要找到的是下标和数字不对应的那个，它就是我们要找的缺失的数字。

### 代码实现： ###

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

## 解题思路二：（数字加减法） ##

用没有缺失的数组中所有数字之和减去缺失了数字的数组所有的数字之和，它们的差就是该缺失的数字。

### 代码实现： ###

class Solution {
        public int missingNumber(int[] nums) {
            int sum=0;//记录没有缺失的和
            int ret=0;//记录缺失的和
            for(int i=0;i<nums.length+1;i++){
                ret+=i;
            }
    
            for(int i=0;i<nums.length;i++){
                sum+=nums[i];
            }
    
            return ret-sum;
    
        }
    }

## 解题思路三：（异或法） ##

`a ^ a = 0`; 一个数异或自己，结果为零。`a ^ 0 = a`; 一个数异或零，结果为它本身  
异或运算满足交换律,结合律 :

a ^ b = b ^ a ; (a ^ b) ^ c = a ^ ( b ^ c ) ;

所以，若 s = a^b^c^d; 如果其中两个数相等，比如 b==c, 则“抵消”，s = a^d。

所以当我们把所有数组下标都异或，并且再异或所有数组中的数字就可以找到缺失的数字，别忘了补上没有缺失的数组的n。

### 代码实现： ###

class Solution {
        public int missingNumber(int[] nums) {
            int ret=0;//用来进行异或运算
    
            //对所有下标和数组中的数字进行异或
            for(int i=0;i<nums.length;i++){
                ret^=i;
                ret^=nums[i];
            }
            //最后别忘了n下标（补上缺失的数字后的数组下标比缺失的多1）
            ret^=nums.length;//n就是nums.length
    
            return ret;
    
        }
    }

## 原题： ##

[189. 轮转数组][189.]

给你一个数组，将数组中的元素向右轮转 `k`个位置，其中 `k`是非负数。

![7f466de69c824d9a847e9687fb819f3c.png][] ![2092f2083f8748dda8c3ea1f8e13a3b8.png][]

## 解题思路： （翻转法） ##

![179f47badbf04b7187a35ac3fdda455c.png][]  
**过程：** ![5018ffd26ebc41e7973ad7ec6fe3bd60.png][]

### 代码实现： ###

class Solution {
        public void rotate(int[] nums, int k) {
            k%=nums.length;//防止k超出数组范围
             reverse(nums,0,nums.length-1);//整体翻转
            reverse(nums,0,k-1);//前部分翻转
            reverse(nums,k,nums.length-1);//后部分翻转
           
    
    
        }
        //自定义翻转方法
        public void reverse(int[] nums,int left,int right){
    
            while(left<right){
            int temp=nums[left];
            nums[left]=nums[right];
            nums[right]=temp;
            left++;
            right--;
            }
           
        }
    }

**空间复杂度为 `O(1)`**

[ced485cbb11e458d81a746890b32cf3f.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/48ff95067f8e4e9dbc5fa22a2328e838.gif
[Link 1]: https://blog.csdn.net/m0_67995737?type=blog
[LeetCode]: https://blog.csdn.net/m0_67995737/category_11942571.html
[Link 2]: https://www.nowcoder.com/link/pc_csdncpt_ylcxx_c
[17.04.]: https://leetcode.cn/problems/missing-number-lcci/
[cafdf39278aa4b2e833a9738f65182a3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/b2ea9116b72c455f9040fa394756ea45.png
[189.]: https://leetcode.cn/problems/rotate-array/
[7f466de69c824d9a847e9687fb819f3c.png]: https://img-blog.csdnimg.cn/7f466de69c824d9a847e9687fb819f3c.png
[2092f2083f8748dda8c3ea1f8e13a3b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/f8d33ffe73eb4a8da4c0deab741bd51a.png
[179f47badbf04b7187a35ac3fdda455c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/9cfac9d7820d40d784bea3927e9d6fce.png
[5018ffd26ebc41e7973ad7ec6fe3bd60.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/342eb6e040f44b2e97c024c6f846f84d.png