成都网站建设的公司哪家好,90设计网站终身会员,设计标志公司,苏州网站开发建设方法数据结构#xff1a;复杂度的练习#xff08;笔记#xff09; 例题一#xff1a; 可以先给数组排序#xff0c;然后再创建一个i值#xff0c;让他循环一次一次#xff0c;遍历这个排序后的数组#xff0c;但如果用qsort函数进行排序#xff0c;时间复杂度就和题目要求…数据结构复杂度的练习笔记 例题一 可以先给数组排序然后再创建一个i值让他循环一次一次遍历这个排序后的数组但如果用qsort函数进行排序时间复杂度就和题目要求的不一致了。所以这个方法行不通 可以将0-n的整数全部相加然后减去数组中的每个元素那么就会得到缺失的那个数此时也会发现时间复杂度是O(N),符合题目的要求。所以这个方法可以 可以创建一个数组arr2将题目给的数组arr1内的数字 作为arr2的下标并且将值放进去。最后如果发现arr2数组内那个坐标没有值那么就是哪个数。发现时间复杂度也是O(N)。所以这个方法也可以。 这里将arr1放入arr2需要循环N次在这个循环外需要遍历arr2中缺失的那个数又需要N次因此F(N) 2N 那么时间复杂度就是O(N) 相比与思路2思路3略比逊色。 异或相同位0.不同为1 两个相同的数字异或是0x^x0 因此x先和[0,n]异或就会拿到[0,n]这些数字也就是x就会被赋予这些数字。当这些数字再在有缺失的数组中异或得到的就会是哪个缺失的数字。 无论数组中的数字是不是[0.n]的顺序只要期间内和相同的数字异或那么就会是0。 如x^y^b^a^y^a^bx^y^y^a^a^b^bx^0^0^0x(缺失的那个数) 因此无论x先和谁异或只要相同的两个数异或过那么就相当于异或上0也就是会被消掉。 最后时间复杂度ON 就用思路4来写一段代码 #define _CRT_SECURE_NO_WARNINGS#include stdio.h
#include stdlib.h
int main()
{int arr1[] { 9,0,1,8,4,6,5,3,7};//缺失2int x 0;int n sizeof(arr1) / sizeof(arr1[0]);//题目中的n是给定的,不算入时间复杂度。for (int i 0; i n; i){x ^ i;i ! n ? x ^ arr1[i] : NULL ;//防止越界访问}printf(%d\n, x);//结果2return 0;
} i ! n ? x ^ arr1[i] : NULL ;使用的是三目运算符(条件运算符)当in时arr1并没有arr1[n]元素如果访问了就是越界访问会出现问题。因此当i时执行NULL,也就是不执行。 例题二 对于这道题有单独的文章 C语言题目:左旋字符串._srhqwe的博客-CSDN博客
方法一对应C语言题目:左旋字符串._srhqwe的博客-CSDN博客的方法一: 空间复杂度是O(1) :因为空间是可以重复利用的tmp被释放掉然后又用tmp。 时间复杂度是O(N*K):保存变量然后旋转n-1次就是N其中要执行K次所以是K*N。 方法二: 开辟一块空间(数组)tmp将要旋转的个数对应nums元素的位置然后直接放到tmp数组在把nums剩下的元素再放到tmp数组。 如此时间复杂度是O(N) 空间复杂度是O(N)但题目要求空间复杂度是O(1)因此这里并不符合题目的要求。 方法三三步反转法对应C语言题目:左旋字符串._srhqwe的博客-CSDN博客的方法二 时间复杂度是O(N)
空间复杂度是O(1) 因为方法1和3在另一篇文章都有,就写一遍方法2但是方法2并不符合题目要求。
#define _CRT_SECURE_NO_WARNINGS#include stdio.h
#include stdlib.hint main()
{int arr[] { 1,2,3,4,5,6,7,8,9 };int tmp[20] { 0 };int sz sizeof(arr) / sizeof(arr[0]);//元素个数int k 3;//假如要向左旋转的字符个数为3for(int i 0;isz-k;i)//将arr后6个放到tmp的前6个当中{tmp[i] arr[k i];}for (int i 0; i k ; i)//将arr前3个放到tmp后3个中{tmp[sz - k i] arr[i];}for (int i 0; i sz; i)//打印tmp的每个元素{printf(%d , tmp[i]);//结果:4 5 6 7 8 9 1 2 3}//实现反转return 0;
}
