【每日易题】数组下标的逆天用法——你见过把数组存储的值当作数组下标来解题的吗？

柔情只为你懂 2024-03-24 21:32 45阅读 0赞

![在这里插入图片描述][3b5ce6acb987412b9ce66515e086c46d.png_pic_center]

[君兮\_的个人主页][Link 1]

**勤时当勉励 岁月不待人**

**C/C++ 游戏开发**

> ***Hello,米娜桑们，这里是君兮\_，在最近是刷题中，遇到了一种非常新奇的数组下标的用法，今天想来给大家分享一下这种神奇的思路和方法，希望能在你遇到类似问题时能通过这种方法快速解决***

#### 数组中消失的它 ####

*  一.题目介绍
 *  二.数组下标的特别用法
 *   *  思路分析
     *  具体详解以及代码
 *  总结

## 一.题目介绍 ##

*  LeetCode此题的oj链接在这里  
    [找到所有数组中消失的数字][Link 2]  
    ![在这里插入图片描述][c36e6fa658f34231a341cad9ba2dff93.png]
 *  **如果你看过我上一篇有关“单身狗”的每日易题的话，你可能会觉得这个题不过就是单身狗问题的一个变种，但是这里最大的问题在于，具体到题目中，我们无法确定有几条“单身狗”，也就是不知道具体有几个消失的数字，因此，大多数人可能会产生这样一种思路，并且写出下面这段代码**

int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize){
        
      
    *returnSize = 0;
    int j = 0;
    int count = 0;
    int size = 0;
    int* returnNum = (int*)malloc(sizeof(int) * (numsSize - 1));
    for (int i = 1; i <= numsSize; i++)
    {
        
        
    
        for (j = 0; j < numsSize; j++)
        {
        
            size = j;
            if (nums[j] == i)
                break;
    
    
        }
    
        if (nums[size] != i)
        {
        
            returnNum[(*returnSize)++] = i;
    
        }
    
    }
    return returnNum;
    }

*  大致的思路是，从1-n，每次都遍历一遍数组，当遍历完一个自然数后，如果数组中没有对应的数字，就说明数组中没有这个数，把它放进需要返回的数组中
 *  这种思路是非常正常并且正确的，但是，很遗憾，是过不了所有测试用例的  
    ![在这里插入图片描述][9d88a06e0da742e5bca0b510f7fb5764.png]
 *  原因很简单，时间复杂度为o(n^2)，一旦给出上图类似的测试用例时，就会超出运行的时间限制，下面我来介绍一种新的思路

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

## 二.数组下标的特别用法 ##

### 思路分析 ###

*  题目的要求是要找的消失的数字，也就是数组中不存在的数字，如果不存在这个数字，那我们如果把数组中的数字作为数组的下标，是不是就找不到消失的数字的数组下标呢？
 *  好好想想上面这句话，我们来进一步思考
 *  如果找不到对应消失数字的下标，那么就会出现这样一种情况，当我们把数组中存放的元素作为数组的下标进行统一的操作，由于不存在消失数字的下标，我们就无法对该消失数字做下标的位置进行操作，这样存在的数字和消失的数字就有了区别，我们就可以判断哪些下标位置的元素没进行某种操作返回下标这种方法来找到我们的消失的数字了（就是此时的下标）

### 具体详解以及代码 ###

> **通过上面的分析，我们可以得到以下的解题思路：  
> 我们首先重置一遍数组中的值，将数组中每个位置存储的值作为操作的数组的下标，将该下标的值改为负值，循环n次后，此时以数组中存放的值的为下标存储的元素全部被改为负值，只有以数组中不存在的值的下标的元素未被修改仍为正值，遍历一遍数组，如果数组下标存储的元素的值为正，说明下标+1就为消失的数字，把它们依次填入需要返回的数组即可**

*  以数组\[ 2,3,3,2,4\]为例  
    ![在这里插入图片描述][b954c81d17574a58b9908372d9e9d751.png]
 *  这里还有几点需要注意的地方
 *  1.我们知道,有消失的数字就一定有重复的数字，因此我们在置负值时，需要先判断一下该下标存储的值是否为负，如果为负，就不需要再改了，同时也是由于这个原因，我们不想看到数组下标出现负数的情况(之前某个位置存储过我们此时的下标，并且我们已经置负了)，因此下标中需要加绝对值
 *  2.由于我们的数组下标是从0开始的，因此我们在返回消失的数字时，应该进行+1还原
 *  源码如下：

int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize){
        
     for(int i=0;i<numsSize;i++)
        {
        
            if(nums[abs(nums[i])-1]>0)//abs置绝对值，-1是因为数组下标从0开始
            nums[abs(nums[i])-1]*=-1;
    
    
        }
        //减一是因为数组中必有一个在1到n中存在的数 比如111111111111111111 一定有1
        int*ret=(int*)malloc(sizeof(int)*(numsSize-1));
        *returnSize=0;
        for(int i=0;i<numsSize;i++)
        {
        
            if(nums[i]>0)
            ret[(*returnSize)++]=i+1;//下标从0开始，消失的数字要+1
        }
        return ret;
    }
    }

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

*  我们这种方法，时间复杂度为O(n),不算需要返回的数组，空间复杂度为O(1)，无疑是非常高效且省内存的。

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

## 总结 ##

*  今天的内容到这里就结束了，如果一时理解不了我的建议是自己带入一些具体的例子画图分析，这样很容易就大致明白每一步操作在干嘛了，如果你明白了的话，不妨自己试着用这种方法来解一下这道题哦！！
 *  好了，如果你有任何疑问欢迎在评论区或者私信我提出，大家下次再见啦！

> ***新人博主创作不易，如果感觉文章内容对你有所帮助的话不妨三连一下这个新人博主再走呗。你们的支持就是我更新的动力！！！***

**\*\*（可莉请求你们三连支持一下博主！！！点击下方评论点赞收藏帮帮可莉吧）\*\***

![在这里插入图片描述][20fa3306e76244de9879742c165c792a.gif_pic_center]

[3b5ce6acb987412b9ce66515e086c46d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/f5c5944a1011483fb4ca261e2e55851f.png
[Link 1]: https://blog.csdn.net/syf666250?spm=1010.2135.3001.5343
[Link 2]: https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array/
[c36e6fa658f34231a341cad9ba2dff93.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/38af5bb4e7ef4b178633ad8835c4d736.png
[9d88a06e0da742e5bca0b510f7fb5764.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/505a3ac463924a0db50cd264c0a6845c.png
[b954c81d17574a58b9908372d9e9d751.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/9283d94bd2d247b4a57bd1abb5bf63a4.png
[1479d43f6dd04f3c821d6e35b6b50f54.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/e8737b54ce35435c8ee8c963330709e4.png
[20fa3306e76244de9879742c165c792a.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/28953a65bdba48b89c01cd41866acf33.png