前引：从此篇文章开始，小编带给大家的是数据结构初阶的刷题讲解 ，此类文章将简略的包含相关知识，详细的思路拆分讲解，分析每一题的难点、易错点，看见题目如何分析，以上就是小编预备的内容，对于数据结构巩固知识的伙伴们来说，可以一试，告别冗杂的知识点，如果伙伴们发现下面哪有有问题，欢迎在评论区指出哦！小编一定会进行修改的！正文开始~
目录
知识点速览
计算时间复杂度
第一题
第二题
第三题
第四题
第五题
第六题
第七题
第八题
计算空间复杂度
第一题
第二题
第三题
复杂度的实际应用
第一题
第二题
知识点速览
复杂度可以分为时间复杂度、空间复杂度，它们都是度量算法优劣的算级说明，通常是估算，采用大O渐进表示法，例如如O（N）
复杂度计算：
时间复杂度是计算执行次数（估算）；空间复杂度看（变量个数+额外开辟空间数）
复杂度种类：复杂度一般有最坏、最好、平均复杂度之分，我们一般取最坏结果
计算步骤：（1）先算出准确执行次数【时间复杂度】 /（变量个数（函数内）+额外空间数量） 【空间复杂度】（2）再根据规则修改
时间复杂度、空间复杂度计算规则：
（1）用常数 1 取代运行时间中所有的加法常数（常数化1）
（2）只要高阶项，不用低阶项（取大舍小）
（3）不要高阶项系数（去系数）
计算时间复杂度
第一题
void Func1(int N)
{int count = 0;for (int i = 0; i < N; i++){for (int j = 0; j < N; j++){++count;}}for (int k = 0; k < 2 * N; k++){++count;}int M = 0;while (M--){++count;}printf("%d\n", count);
}按照上面的计算步骤：先算总的执行次数，可以算出准确次数为：N*N + 2N，再根据计算规则（取大舍小），最终得到它的时间复杂度用大O渐进表示法得到 O（N^2）
第二题
void Func2(int N)
{int count = 0;for (int k = 0; k < 2 * N; k++){++count;}int M = 0;while (M--){++count;}printf("%d\n", count);
}根据计算步骤，得到总的执行次数为：2N，再根据计算规则（去系数），得到最后它的时间复杂度用大O渐进表示法表示为O（N）
第三题
void Func3(int N,int M)
{int count = 0;for (int k = 0; k < N; ++k){++count;}for (int k = 0; k < M; ++k){++count;}
}按照计算步骤，我们先算出准确的执行次数为N+M，这里出现一个问题，如果按照取大舍小，我们是无法判断的，因为M、N都是未知数
分析：如果M较大，那就舍弃N；如果M较小，那就舍弃M；如果M等于N，那就是2M或者2N
对于这种情况，我们是都不能舍弃的，只能都保存，因此最后的时间复杂度是O（M+N）
第四题
void Func4(int N)
{int count = 0;for (int k = 0; k < 100; k++){++count;}printf("%d\n", count);
}根据计算步骤，我们先算出准确的执行次数为100次，再根据计算规则常数化1，得到最后的时间复杂度用大O渐进表示法表示为O（1）
第五题
const char* strchr(const char* str, char character)
{while (*str != '\0'){if (*str == character){return str;}++str;}return NULL;
}首先根据计算步骤，我们需要先计算准确执行次数，这题同样有一个问题，就是不知道这个字符串的长度，所以我们需要分类：
最好情况：直接出循环，1次执行次数（总执行次数）
最坏情况：假设字符串长度N，它找到底才找到，也就是N次（总执行次数）
按照计算规则，选择最坏情况，时间复杂度表示为O（N）
第六题
void BubbleSort(int* a, int n)
{assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i - 1] > a[i]){Swap[&a[i - 1], &a[i]];exchange = 1;}}if (exchange == 0){break;}}return;
}按照计算步骤，先算总的执行次数，通过代码我们看到，还是需要分类考虑
最好情况：进入外面的 for 循环一次，里面的循环需要走 end 次，总的执行次数就是 end+1 次
最坏情况：那就只能把循环走完了！总的执行次数也就是 end^2 次
再根据计算规则，取最坏情况，得到最后的时间复杂度为O（N^2）
易错点：首先小编也经历过这个雷区！经常以为双层for循环就是N^2了，一层for循环就是N次，但是需要避雷这个，具体情况需要具体分析，我们继续向下看！
第七题
int BinarySearch(int* a, int n, int x)
{assert(a);int begin = 0;int end = n;while (begin < end){int mid = begin + ((end - begin) >> 1);if (a[mid] < x){begin = mid + 1;}else if (a[mid] > x){end = mid;}elsereturn mid;}return -1;
}首先我们先来计算它的总次数，根据这个代码情况，属于二分查找，还是需要分类
最好情况：那肯定就一次找到，总执行次数就是1次
最坏情况：对一组数据一直二分下去，要找的元素在数组最后一个被检查的位置
假设数组长度为N，每经过一次二分，剩余元素为N/2，经过 k 次后，剩余元素为N/ （2^k）
最坏情况也就是当剩余元素为1时，即N/（2^k）=1
解得k=log N（注意log N在复杂度里面是等于㏒以2为底N的对数的）
按照计算规则，取最坏情况，得到最后的时间复杂度为 log N
第八题
long long Factorial(size_t N)
{return N < 2 ? N : Factorial(N - 1) * N;
}首先根据计算步骤，计算总的执行次数，我们发现这是一个三目操作符，我先来简答解释一下它的运算思路：
如果N<2，为真就得到结果N，如果为假就得到结果 Factorial（N-1）*N
因此我们发现这是一个计算前 n 项阶层的递归函数，下面我们来分析
最好情况：直接执行一次，即计算 1 的前 n 阶层
最坏情况：假设有N个数字，那么它的阶层就是N*（N-1）*（N-2）*（N-3）......，执行了N次
根据计算规则，保留最坏情况，得到最后的时间复杂度为O（N）
计算空间复杂度
第一题
void BubbleSort(int* a, int n)
{assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i - 1] > a[i]){Swap[&a[i - 1], &a[i]];exchange = 1;}}if (exchange == 0){break;}}return;
}首先我们按照计算步骤，先算（变量个数+额外空间数），上面总共有3个变量，没有开辟额外的空间，因此准确计算得到数量为3
再按照复杂度的计算规则（常数化1），得到最后的空间复杂度为O（1）
第二题
long long* Fibonacci(size_t n)
{if (n == 0){return NULL;}long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
}
首先我们按照计算步骤，先算（变量数+额外空间数），这个函数没有变量，但是它额外开辟了（n+1）的空间个数，因此总的数量就是 0+（n+1）= N+1
根据计算规则（舍大取小），得到最后的空间复杂度为O（N）
第三题
long long Factorial(size_t N)
{return N < 2 ? N : Factorial(N - 1) * N;
}这是一个计算 N 的阶层积的函数，比如N*（N-1）*（N-2）*（N-3）*........
每次递归都需要开辟函数栈帧空间，这里是从N-1开始调用递归函数的，因此是N-1个额外空间，没有其它变量，所以得到总的数量是0+（N-1）= N-1
根据计算规则（舍大取小），得到最后的空间复杂度为O（N）
复杂度的实际应用
话不多说我们通过两道例题来看看复杂度的实际应用
第一题
上面我们看到它的要求是时间复杂度不能超过O（N），这就是复杂度在实际的应用，题目可能会规定一定的时间复杂度、空间复杂度，下面我们开始解决这个问题！
（1）最简单的方法就是：计算 0~N 的数字之和，再减去题目中已有的数字，这样我们就找到了 那个缺失的数字，大家不能理解的话欢迎在评论区留言啊！下面我们来实现代码：
int missingNumber(int* nums, int numsSize)
{int sum = 0;//求和for (int i = 0; i <= numsSize; i++){sum += i;}//求差for (int i = 0; i < numsSize; i++){sum -= nums[i];}return sum;
}（2）算法解法：我们先来了解一个运算符^ ,它比较的是二进制位，相同为0，相异为1，例如：
3的二进制是：00000000 00000000 00000000 00000011
1的二进制是：00000000 00000000 00000000 00000001
1^2^3的二进制是：00000000 00000000 00000000 00000011
将1^2^3的二进制分别与3、2的二进制去异或，这样我们就得到了中间的2的二进制
算法实现：我们把0~N的数字去分别异或，然后再将异或得到的结果与题目中数组的每个元素异或，那样就找到了少的那个数字（一般用0去开始异或，因为0与任何数异或都为那个数字）
int missingNumber(int* nums, int numsSize)
{//0与任何数异或都为那个数，不会产生影响int n = 0;//分别异或0~N的数字for (int i = 0; i <= numsSize; i++){n ^= i;}//再与0~N-1的数字异或，得到差值for (int i = 0; i < numsSize; i++){n ^= nums[i];}return n;
}第二题
首先我们我们来说一下几种解法：
（1）暴力解法：一次旋转一位数字，通过移动其余元素达到目标，但是效率上无法通过
（2）间接解法：将后k个元素拷贝到另外一个数组，再将前n-k个元素拷贝过来，再进行整体拷 贝，但是这样就不是原地了，也无法达到更高的进阶要求
（3）算法解法：我们先将数组的前n-k个元素旋转交换位置，再将后k个元素旋转位置，再整体旋 转交换位置，拿时间换取空间。例如下面这样：
void Exchange(int* p1, int* p2)
{int num = *p1;*p1 = *p2;*p2 = num;
}
int* missNumber(int* nums, int numsSize)
{//旋转前numsSize-k个元素int i = 0;int j = numsSize - k - 1;while (i < j){Exchange(&nums[i], &nums[j]);i++;j--;}//旋转后k个元素i = numsSize - k - 1;j = numsSize - 1;while (i < j){Exchange(&nums[i], &nums[j]);i++;j--;}//旋转整体i = 0;j = numsSize - 1;while (i < j){Exchange(&nums[i], &nums[j]);i++;j--;}return nums;
}
