【初阶数据结构与算法 2】时间/空间复杂度练习——转轮数组
前言
前面学习了时间复杂度和空间复杂度相关的知识点,本文将通过练习题转轮数组,来巩固所学知识。
1、转轮数组
实现一个函数,可以轮转数组中的k个元素,例如:
1 2 3 4 5 6 7
轮转3个元素,
即将 5 6 7 放到数组前面,得到
5 6 7 1 2 3 4
2、 方法1——数组
- 时间复杂度:O(k*N),
- 内循环N次,外循环k次,k 最坏是 N-1,最好情况是 1
- 空间复杂度:O(1)
- 算法额外临时创建了3个变量
void leftChange1(int a[], int sz, int cnt)
{
int tmp = 0;
cnt = cnt % sz;//表示旋转几个字符,当轮转个数大于数组长度时,取模
for (int k = 0 ; k < cnt; k++)
{
tmp = a[sz-1];
for (int i = sz - 2; i >= 0; i--)
{
a[i+1] = a[i];//前面一项赋值给后一项
}
a[0] = tmp;
}
}
3、 方法2——指针
方法2和方法1没有区别
//基础解法2 用指针
void leftChange2(int* a, int sz, int cnt)
{
int tmp = 0;
cnt = cnt % sz;//表示旋转几个字符
for (int k = 0; k < cnt; k++)
{
tmp = *(a + sz -1);
for (int i = sz - 2; i >=0 ; i--)
{
*(a + i + 1) = *(a + i);
}
*a = tmp;
}
}
4、 方法3——动态内存空间
用指针、字符串库函数、动态内存空间
- 时间复杂度:O(N),数组a拷贝到pc,执行N次,在拷贝回a也是N次
- 空间复杂度:O(N),算法临时开辟了N个空间
void leftChange3(int* a, int sz, int cnt)
{
cnt = cnt % sz;
int* pc = (int*)malloc(sz*sizeof(int));
if (pc == NULL)
{
perror("malloc:");
return;
}
memcpy(pc, a + sz - cnt, cnt * sizeof(int));//
memcpy(pc + cnt, a , (sz-cnt) * sizeof(int));//
memcpy(a, pc, sz*sizeof(int));//
free(pc);
pc = NULL;
}
5、 方法4——3次逆转
3次逆转,很难想到
- 时间复杂度:O(N),数组a前半后半分别逆转,执行N次,最后整体逆转也是N次
- 空间复杂度:O(1),算法临时建立了1N个临时变量
void reverse(int* a, int left, int right)
{
while (left < right)
{
char tmp = a[left];
a[left] = a[right];
a[right] = tmp;
left++;
right--;
}
}
void leftChange4(int* num, int sz, int cnt)
{
cnt = cnt % sz;
reverse(num, sz - cnt, sz-1);//后半部分
reverse(num , 0 , sz-cnt-1);//前半部分
reverse(num, 0, sz - 1);
}
int main()
{
int a[] = { 1,2,3,4,5,6,7 };
int sz = sizeof(a)/sizeof(a[0]);//数组个数
//leftChange1(a, sz, 3);
//leftChange2(a, sz, 3);
//leftChange3(a, sz, 3);
leftChange4(a, sz, 3);
for (int i = 0; i < sz; i++)
{
printf("%d ", a[i]);
}
return 0;
}
总结
时间复杂度和空间复杂度要牢记定义,多练习才能熟练掌握。
要做到不写代码,只分析思路就能知道时间复杂度的阶数。
初阶数据结构和算法建立在C语言之上的,学习这部分内容,要随时复习之前所学的知识。
下一篇将继续练习。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
二维码