转轮数组

  • 前言
  • 1、转轮数组
  • 2、 方法1——数组
  • 3、 方法2——指针
  • 4、 方法3——动态内存空间
  • 5、 方法4——3次逆转
  • 总结

前言

前面学习了时间复杂度和空间复杂度相关的知识点，本文将通过练习题转轮数组，来巩固所学知识。

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语言之上的，学习这部分内容，要随时复习之前所学的知识。

下一篇将继续练习。