时间复杂度空间复杂度相关练习题

骑猪看日落 2023-10-14 16:41 41阅读 0赞

### 1.消失的数字 ###

【题目】：[题目链接][Link 1]

![dc561b3467f6497786bff130fbec033a.png][]

思路1：排序——》qsort快排——》时间复杂度O（n\*log2n） 不符合要求

**思路2：**（0+1+2+3+...+n)-(a\[0\]+a\[1\]+\[2\]+...+a\[n-2\]) ——》

时间复杂度O（N）空间复杂度为O（1）

（0+1+2+3+...+n)直接用等差数列求和就可

思路3：数组中是几就在第几个位置写一下这个值 ——》时间空间复杂度都为O（N）

**思路4：**给一个值x=0，

x先跟\[0,n\]的所有值异或，

x再跟数组中的每个值异或，最后x就是缺的那个数字

（**异或的特点相同的数异或为0，0跟一个数异或为这个数，且异或满足交换律**）

时间复杂度O（N） 空间复杂度O（1）

eg：假设\[0,9\]缺一个8，先让x=0跟\[0,9\]不缺8的数一个一个异或（0跟一个数异或为这个数，这样初始化以后就不会被x所影响），异或完的结果还是\[0,9\],然后这些值和缺8的数组异或，结果发现这两个数组中相同的两个数异或为0就没了（可以直接交换律理解），最后只剩下0和8异或，异或结果就是8（也就是缺少的数字）

**【图解】：**![ba2988147f9149c8bc736ad67dab268c.jpeg][]

本题推荐思路2和思路4：时间空间复杂度最优

思路2代码实现：

int missingNumber(int* nums, int numsSize)
    {
        //等差数列求和
       int sum=((1+numsSize)*numsSize)/2;
       //sum减去数组中的元素
       for(int i=0;i<numsSize;i++)
       {
           sum-=nums[i];
       }
        return sum;
    }

思路4代码实现：

int missingNumber(int* nums, int numsSize){
        int x=0;
        //跟数组中的值异或
        for(int i=0;i<numsSize;i++)//这里少一个数，直接<
        {
            x^=nums[i];
        }
        //跟[0,9]的值异或
        for(int i=0;i<=numsSize;i++)//这里多一个数（n+1）个，<=
        {
            x^=i;
        }
    
        return x;
    }

### 2.旋转数组 ###

【题目】：[题目链接][Link 2]

![c33817fcfc8b42fe939ef81301ffc82f.png][] ![f67234ec0ab04dac9ff7c519d4b546b1.png][]

思路1：暴力求解，旋转K次（一次一次地移，直到旋转

时间复杂度：O（N\*K）空间复杂度：O（1）

思路2：开辟额外空间，以空间换时间

（创建一个数组，要移动到前面的就放入数组，其他部分向后移动即可）

时间复杂度：O（N） 空间复杂度：O（N）

> **思路3：**（1）前n-k个数字逆置
> 
>  （2）后k个逆置
> 
>  （3）整体逆置
> 
> 时间复杂度：O（N） 空间复杂度：O（1）

这里肯定是思路3最优

代码演示：

void reverse(int *nums,int left,int right)
    {
        while(left<right)
        {
            int tmp=nums[left];
            nums[left]=nums[right];
            nums[right]=tmp;
            left++;
            right--;
        }
    }
    void rotate(int* nums, int numsSize, int k)
    {
        k=k%numsSize;
        //倒置前n-k个数字
        reverse(nums,0,numsSize-k-1);
        //倒置后k个数字
        reverse(nums,numsSize-k,numsSize-1);
        //倒置整个数组
        reverse(nums,0,numsSize-1);
    }

k=k%numsSize;的意思就是如果k的大小大于numsSize的大小，那么就需要对k进行取模操作，这样避免重复操作，效率更高

本次数据结构时间空间复杂度练习的内容就到此啦，有什么问题欢迎评论区或者私信交流，觉得笔者写的还可以，或者自己有些许收获的，麻烦铁汁们动动小手，给俺来个一键三连，万分感谢 !

![f1a886e180c14013956b3e693ea6ec5e.jpeg][]

[Link 1]: https://leetcode.cn/problems/missing-number-lcci/submissions/
[dc561b3467f6497786bff130fbec033a.png]: https://img-blog.csdnimg.cn/dc561b3467f6497786bff130fbec033a.png
[ba2988147f9149c8bc736ad67dab268c.jpeg]: https://img-blog.csdnimg.cn/ba2988147f9149c8bc736ad67dab268c.jpeg
[Link 2]: https://leetcode.cn/problems/rotate-array/
[c33817fcfc8b42fe939ef81301ffc82f.png]: https://img-blog.csdnimg.cn/c33817fcfc8b42fe939ef81301ffc82f.png
[f67234ec0ab04dac9ff7c519d4b546b1.png]: https://img-blog.csdnimg.cn/f67234ec0ab04dac9ff7c519d4b546b1.png
[f1a886e180c14013956b3e693ea6ec5e.jpeg]: https://img-blog.csdnimg.cn/f1a886e180c14013956b3e693ea6ec5e.jpeg