1.消失的数字
【题目】：题目链接
思路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（也就是缺少的数字）
【图解】：
本题推荐思路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.旋转数组
【题目】：题目链接
思路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进行取模操作，这样避免重复操作，效率更高
本次数据结构时间空间复杂度练习的内容就到此啦，有什么问题欢迎评论区或者私信交流，觉得笔者写的还可以，或者自己有些许收获的，麻烦铁汁们动动小手，给俺来个一键三连，万分感谢 !
