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进行取模操作,这样避免重复操作,效率更高
本次数据结构时间空间复杂度练习的内容就到此啦,有什么问题欢迎评论区或者私信交流,觉得笔者写的还可以,或者自己有些许收获的,麻烦铁汁们动动小手,给俺来个一键三连,万分感谢 ! 文章来源:https://www.toymoban.com/news/detail-640946.html
文章来源地址https://www.toymoban.com/news/detail-640946.html
到了这里,关于时间复杂度空间复杂度相关练习题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!