【初阶数据结构与算法 2】时间复杂度与空间复杂度（2）——转轮数组、左旋字符、消失的数字

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

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

实现一个函数，可以轮转数组中的k个元素，例如：

1 2 3 4 5 6 7 
轮转3个元素，
即将 5 6 7 放到数组前面，得到
5 6 7 1 2 3 4

• 时间复杂度：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;
  }
  }

方法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;
	}
}

用指针、字符串库函数、动态内存空间

• 时间复杂度：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(szsizeof(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, szsizeof(int));//
  free(pc);
  pc = NULL;
  }

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

下一篇将继续练习。