开发一个电商网站,河北省工程建设信息网,上海wordpress网站建设,专业做网站多少钱1.消失的数字
【题目】#xff1a;题目链接 思路1#xff1a;排序——》qsort快排——》时间复杂度O#xff08;n*log2n#xff09; 不符合要求
思路2#xff1a;#xff08;0123...n)-(a[0]a[1][2]...a[n-2]) ——》
时间复杂度O#xff08;N#xff09;空间复杂度…1.消失的数字
【题目】题目链接 思路1排序——》qsort快排——》时间复杂度On*log2n 不符合要求
思路20123...n)-(a[0]a[1][2]...a[n-2]) ——》
时间复杂度ON空间复杂度为O1
0123...n)直接用等差数列求和就可
思路3数组中是几就在第几个位置写一下这个值 ——》时间空间复杂度都为ON
思路4给一个值x0
x先跟[0,n]的所有值异或
x再跟数组中的每个值异或最后x就是缺的那个数字
异或的特点相同的数异或为00跟一个数异或为这个数且异或满足交换律
时间复杂度ON 空间复杂度O1
eg假设[0,9]缺一个8先让x0跟[0,9]不缺8的数一个一个异或0跟一个数异或为这个数这样初始化以后就不会被x所影响异或完的结果还是[0,9],然后这些值和缺8的数组异或结果发现这两个数组中相同的两个数异或为0就没了可以直接交换律理解最后只剩下0和8异或异或结果就是8也就是缺少的数字
【图解】 本题推荐思路2和思路4时间空间复杂度最优
思路2代码实现
int missingNumber(int* nums, int numsSize)
{//等差数列求和int sum((1numsSize)*numsSize)/2;//sum减去数组中的元素for(int i0;inumsSize;i){sum-nums[i];}return sum;
}
思路4代码实现
int missingNumber(int* nums, int numsSize){int x0;//跟数组中的值异或for(int i0;inumsSize;i)//这里少一个数直接{x^nums[i];}//跟[0,9]的值异或for(int i0;inumsSize;i)//这里多一个数n1个{x^i;}return x;
}
2.旋转数组
【题目】题目链接 思路1暴力求解旋转K次一次一次地移直到旋转
时间复杂度ON*K空间复杂度O1
思路2开辟额外空间以空间换时间
创建一个数组要移动到前面的就放入数组其他部分向后移动即可
时间复杂度ON 空间复杂度ON 思路31前n-k个数字逆置 2后k个逆置 3整体逆置 时间复杂度ON 空间复杂度O1 这里肯定是思路3最优
代码演示
void reverse(int *nums,int left,int right)
{while(leftright){int tmpnums[left];nums[left]nums[right];nums[right]tmp;left;right--;}
}
void rotate(int* nums, int numsSize, int k)
{kk%numsSize;//倒置前n-k个数字reverse(nums,0,numsSize-k-1);//倒置后k个数字reverse(nums,numsSize-k,numsSize-1);//倒置整个数组reverse(nums,0,numsSize-1);
}
kk%numsSize;的意思就是如果k的大小大于numsSize的大小那么就需要对k进行取模操作这样避免重复操作效率更高
本次数据结构时间空间复杂度练习的内容就到此啦有什么问题欢迎评论区或者私信交流觉得笔者写的还可以或者自己有些许收获的麻烦铁汁们动动小手给俺来个一键三连万分感谢 !
