- 前言
- 5、转轮数组
- 5.1 方法1——数组
- 5.2 方法2——指针
- 5.3 方法3——动态内存空间
- 5.4 方法4——3次逆转
- 6、左旋字符
- 6.1 方法1——数组
- 6.2 方法2——指针
- 6.3 方法3——动态内存空间
- 6.4 方法4——3次逆转
- 7、消失的数字
- 7.1 方法1——遍历数组
- 7.2 方法2——求和
- 7.3 方法3——异或
- 总结
前言
上一篇学习了时间复杂度和空间复杂度相关的知识点，本文将通过 3 个练习，来巩固所学知识，主要内容包括：
- 转轮数组
- 左旋字符
- 消失的数字
5、转轮数组 5.1 方法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;
}
}
5.2 方法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;
}
}
5.3 方法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 方法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;
}
6、左旋字符
实现一个函数，可以左旋字符串中的k个字符，例如：
ABCD左旋一个字符得到BCDA ABCD左旋两个字符得到CDAB
通过题目思路分析可以发现：
- 左旋字符和轮转数组实现原理雷同
- 两者知识方向不同，一个向右，一个向左
- 左旋字符的时间复杂度、空间复杂度计算与轮转数组的复杂度计算相同
//基础解法1 用数组
void leftChange1(char a[],int cnt)
{
int tmp = 0;
int len = strlen(a);//4
cnt = cnt % len;//表示旋转几个字符
for (int k = 0; k < cnt; k++)
{
tmp = a[0];
for (int i = 0; i < len; i++)
{
a[i] = a[i + 1];
}
a[len - 1] = tmp;
}
}
6.2 方法2——指针
方法2和方法1没有区别
//基础解法2 用指针
void leftChange2(char* a, int cnt)
{
int tmp = 0;
int len = strlen(a);//4
cnt = cnt % len;//表示旋转几个字符
for (int k = 0; k < cnt; k++)
{
tmp = *a;
for (int i = 0; i < len; i++)
{
*(a + i) = *(a + i + 1);
}
*(a + len-1)= tmp;
}
}
6.3 方法3——动态内存空间
//解法3 用指针、字符串库函数、动态内存空间
//方法2 分两半直接copy,最后在合并一起copy回去
void leftChange3(char* a, int cnt)
{
int len = strlen(a);
cnt = cnt % len;
char* pc = (char*)malloc(len + 1);
if (pc == NULL)
{
perror("malloc:");
return;
}
strcpy(pc, a + cnt);//字符串库函数
strncat(pc, a ,cnt);
strcpy(a, pc);
free(pc);
pc = NULL;
}
6.4 方法4——3次逆转
//方法4 3次逆转，很难想到
void reverse(char* left, char* right)
{
while (left < right)
{
char tmp = *left;
*left = *right;
*right = tmp;
left++;
right--;
}
}
void leftChange4(char* a, int cnt)
{
int len = strlen(a);
cnt = cnt % len;
reverse(a, a + cnt - 1);
reverse(a + cnt, a + len - 1);
reverse(a, a + len - 1);
}
int main()
{
char a[] = "abcd";
//leftChange1(a, 2);
//leftChange2(a, 2);
//leftChange3(a, 2);
leftChange4(a, 2);
printf("%sn", a);
return 0;
}
7、消失的数字
数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数，例如：
输入：[9,6,4,2,3,5,7,0,1] 输出：87.1 方法1——遍历数组
- 时间复杂度：O(N)，数组先后共遍历执行 3N 次
- 空间复杂度：O(N)，算法临时开辟了 N+1 个空间
void searchnum1(int a[], int sz)
{
int cnt = 0;
int* str = (int*)malloc((sz+1) * sizeof(int));
int* pa = str;
if (pa == NULL)
{
perror("malloc:");
return;
}
for (int i = 0; i < (sz+1); i++)
{
pa[i] = -1;//初始化为0
}
for (int i = 0; i < sz ; i++)
{
pa[(a[i])] = a[i];
}
while (*pa!=-1)
{
pa++;//这里pa不是起始位置了，不能释放了，所有会报错,用str记住初始位置
cnt++;
}
//pa = pa - cnt;//将指针弄到起始位置，才能释放
printf("%dn", cnt);
free(str);
str = NULL;
}
7.2 方法2——求和
- 时间复杂度：O(N)，两个循环，共执行 2N 次
- 空间复杂度：O(1)，算法临时建立了 3 个临时变量
void searchnum2(int a[], int sz)
{
int sum = 0;
for (int i = 0; i < sz + 1; i++)
{
sum += i;//n+1个数求和
}
for (int i = 0; i < sz ; i++)
{
sum -= a[i];//剩下的就是空缺的数字
}
printf("%dn", sum);
}
7.3 方法3——异或
异或不容易想到，在基础阶段已经学过异或了，【C语言基础8——操作符详解（1）】4. 位操作符：
异或： 相同为0，相异为1 0000 0 0101 5 0101 5 = 0^5 的结果 0101 5 0100 4 0001 1 = 5^4 的结果 0101 5 0100 4 = 1^5 的结果 0^5^4^5 = 4，从上面的例子可以看出，出现偶数次的数字会抵消掉
- 时间复杂度：O(N)，两个循环，共执行 2N 次
- 空间复杂度：O(1)，算法临时建立了 3 个临时变量
void searchnum3(int a[], int sz)
{
int num = 0;
for (int i = 0; i < sz + 1; i++)
{
num ^= i;
}
for (int i = 0; i < sz; i++)
{
num ^= a[i];
}
printf("%dn", num);
}
int main()
{
int a[] = { 9,6,4,2,3,5,7,0,1 };
int sz = sizeof(a) / sizeof(a[0]);
//searchnum1(a, sz);
//searchnum2(a, sz);
searchnum3(a, sz);
return 0;
}
总结
时间复杂度和空间复杂度要牢记定义，多练习才能熟练掌握。
要做到不写代码，只分析思路就能知道时间复杂度的阶数。
初阶数据结构和算法建立在C语言之上的，学习这部分内容，要随时复习之前所学的知识。
下一篇将学习新的知识点顺序表。
