C 408—《数据结构》算法题基础篇—数组（通俗易懂）

目录

Δ前言

一、数组的合并

        0.题目：

        1.算法设计思想：

        2.C语言描述：

        3.算法的时间和空间复杂度 : 

二、数组元素的倒置

        0.题目 : 

        1.算法设计思想 : 

        2.C语言描述 : 

        3.算法的时间和空间复杂度 : 

三、数组中特定值元素的删除

        0.题目 : 

        1.算法设计思想 : 

        2.C语言描述 : 

        3.算法的时间和空间复杂度 : 

四、数组中值位于某一区间的元素的删除

        0.题目 : 

        1.算法设计思想 : 

        2.C语言描述 : 

        3.算法的时间和空间复杂度 : 

五、数组的去重

        0.题目 : 

        1.算法设计思想 : 

        2.C语言描述 : 

        3.算法的时间和空间复杂度 : 

六、数组中两个子数组的位置互换

        0.题目 : 

        1.算法设计思想 : 

        2.C语言描述 : 

        3.算法的时间和空间复杂度 : 

七、数组元素的循环移动 [2010真题]

        0.题目 : 

        1.算法设计思想 :

        2.C语言描述 : 

        3.算法的时间和空间复杂度 : 

Δ总结

Δ前言

  • 从408应试的角度来看，算法题主要分为四部分——①线性表(包括数组和链表)；②二叉树；③图；④查找。本篇博文主要讲数组相关的基础算法。
  • 博文中涉及到的题目全部参考自《王道数据结构考研复习指导》和《竟成408考研复习全书》。
  • 注意事项——①点击文章侧边栏目录或者文章开头的目录可以进行跳转。②所有题目都符合408算法题的题目格式，即第一问算法设计思想、第二问C语言描述该算法、第三问计算该算法的时空复杂度。
  • 良工不示人以朴，up所有文章都会适时补充完善。大家如果有问题都可以在评论区进行交流或者私信up。感谢阅读！

一、数组的合并

        0.题目：

        现有两个有序的并且是升序的顺序表，要求将这两个顺序表合并为一个新的有序顺序表，并且合并后整个顺序表仍然保持升序，实现该算法的函数需要有返回结果。请设计一个算法来实现上述操作，用C语言描述该算法，并且计算出该算法的时间复杂度和空间复杂度。

        1.算法设计思想：

        “两个有序表合并为一个新的有序表”是一个经典的算法问题。

        它的算法思想是——假设两个升序表分别为a和b，合并后的新的顺序表为c，从头到尾依次比较a和b中的元素，并把更小的那个元素放在c中，直到合并完毕；

        若顺序表a中的元素已经全部复制到了新的顺序表c中，而顺序表b中此时还有未比较的元素，说明顺序表b要比顺序表a更长，且顺序表b中剩余的元素都比新顺序表c中已经有的元素更大，此时，只需要将顺序表b中剩余的元素全部复制到c中即可；反之亦然。

        那么，具体用代码怎么实现呢？

        我们可以用三个变量i, j, k分别表示顺序表a, b, c的下标，并且i, j, k的初始值都为0，如果a[i] <= b[j]，说明a顺序表的第一个元素要比b顺序表的第一个元素更小，所以此时要将这个更小的元素放到新的顺序表中，即“c[k++] = a[i++];”，既传递了值又移动了下标。如果判断不成立，说明b顺序表的第一个元素更小，那我们就要执行“c[k++] = b[j++];”，之后元素的判断都符合这个逻辑。当然，这只是执行的思路，具体的实现我们还可以加入对结构体的数据定义，还可以通过指针变量得到合并后的新的顺序表，请看下文具体的代码实现。

        2.C语言描述：

                完整代码如下：(注意看注释)

# include <stdio.h>
# include <stdlib.h>
# include <stdbool.h>       //or "typedef enum { false, true } bool;"# define MAX_SIZE 100//定义数据结构(Sequential List)
typedef struct SqList {int data[MAX_SIZE];     //data数组存放顺序表中的元素int length;             //length表示顺序表当前存放的元素的个数int capacity;           //capacity表示预分配的数组容量，即最多可存放的元素个数
} SqList;   //函数声明
void initialize(SqList * L);
bool mergeTwo(SqList a, SqList b, SqList * c);int main(void) {SqList a,b,c;initialize(&a);initialize(&b);initialize(&c);//给出两个升序的顺序表，用于测试该算法int array_a[] = {1,2,5,7,9,11,660,880};int array_b[] = {1,3,4,6,10};for (int i = 0; i < 8; ++i) a.data[i] = array_a[i];for (int j = 0; j < 5; ++j) b.data[j] = array_b[j];a.length = 8;b.length = 5;bool point = false;point = mergeTwo(a,b,&c);printf("合并成功了吗———%s\n",point ? "Yes" : "No");printf("合并后的数组是———");for (int i = 0; i < c.length; ++i) {printf("%d ",c.data[i]);}printf("合并后数组的长度是：%d\n",c.length);return 0;
}//初始化数组的方法
void initialize(SqList * L) {L->length = 0;L->capacity = MAX_SIZE;
}//实现“顺序表合并”算法的核心方法(通过指针传递，可以让我们操作合并后的数组)
bool mergeTwo(SqList a, SqList b, SqList * c) {int i = 0, j = 0, k = 0;                //i,j,k分别用于表示a,b,c数组的下标if ((a.length + b.length) > c->capacity) {return false;                       //如果新数组的容量不足以容纳合并后的所有元素，则直接返回false。}while (i < a.length && j < b.length) {  //只要顺序表a和b中还有元素没有合并完成，就继续进行合并if (a.data[i] <= b.data[j]) {c->data[k++] = a.data[i++];} else {c->data[k++] = b.data[j++];}}while (i < a.length) {                  //如果a中还有剩余的元素，就直接复制到c中c->data[k++] = a.data[i++];}while (j < b.length) {c->data[k++] = b.data[j++];         //如果b中还有剩余的元素，就直接复制到c中}c->length = k;                          //最后别忘记设置新数组的长度return true;
}

                运行结果 : 

        3.算法的时间和空间复杂度 : 

        (1) 时间复杂度：

        实现合并算法的第一个while循环最多执行 n + m 次，因为每次迭代，i 或 j 都会增加 1，直到其中一个数组被完全处理；后两个while循环只有一个会执行，并且最多执行 n 或 m 次。所以算法的时间复杂度是O(m+n) + O(max{m,n}) = O(m+n)。
        (2) 空间复杂度：

        因为我们创建了一个新的数组来存储合并后的结果，其大小等于两个输入数组的总长度。所以空间复杂度也为O(m+n)。

二、数组元素的倒置

        0.题目 : 

        有一个长度为n的顺序表L，现要求将顺序表L的所有元素进行倒置。请设计一个算法来实现上述操作，用C语言描述该算法，并且计算出该算法的时间复杂度和空间复杂度。

        1.算法设计思想 : 

        所有元素进行倒置，也就是数组的头尾元素依次进行交换，数组第一个元素和最后一个元素进行交换，数组第二个元素和倒数第二个元素进行交换，以此类推，如果数组中有偶数个元素，正好两两交换完成；如果数组中有奇数个元素，那么中间那个元素就不会被操作。

        那么，如何实现交换操作呢？

        借助临时变量temp来实现。比方说用i 表示数组下标，则需要执行“temp = array[i]; array[i] = array[n-1-i]; array[n-1-i] = temp;”来实现数组首尾元素的交换；交换完成后，需要移动下标i直到数组中间的那个元素，可以借助for循环来实现。(PS : n是数组的长度，所以n - 1就是数组最后一个元素的下标。

        2.C语言描述 : 

                完整代码如下：(注意看注释) 

# include <stdio.h>
# include <stdlib.h># define MAX_SIZE 100//定义数据结构(Sequential List)
typedef struct SqList {int data[MAX_SIZE];int length;int capacity;
} SqList;//函数声明
void initialize(SqList * L);
void reverseArray(SqList * L);int main(void) {SqList array;initialize(&array);//给出一个具体的顺序表，用于测试该算法int array_demo[] = {1,2,3,5,7,9,11};for (int i = 0; i < 7; ++i) array.data[i] = array_demo[i];array.length = 7;reverseArray(&array);for (int i = 0; i < 7; ++i) printf("倒置后的数组的第%d个元素是%d\n",(i+1),array.data[i]);return 0;
}//初始化数组的方法
void initialize(SqList * L) {L->length = 0;L->capacity = MAX_SIZE;
}//实现“数组倒置”算法的核心方法
void reverseArray(SqList * L) {int i, temp = 0;                    //i作为数组的元素下标，temp作为实现交换操作的临时变量int n = L->length;for (i = 0; i < n / 2; ++i) {       //尤其注意控制条件语句“i < n / 2”,若误写成了“i < n”，数组就会被倒置两次。temp = L->data[i];L->data[i] = L->data[n - 1 - i];L->data[n - 1 - i] = temp;}
}

                运行结果 : 

        3.算法的时间和空间复杂度 : 

        (1) 时间复杂度：

        实现倒置算法的核心方法reverseArray中，尽管for循环只执行了n/2次，但for循环的执行次数与问题规模n成正比例关系，所以时间复杂度为O(n)。这是数组倒置最优的时间复杂度，因为我们至少要将数组中的每一个元素都遍历一次。
        (2) 空间复杂度 : 

        由于我们只使用了i，temp，n这几个单独的变量来辅助算法的实现，它们不依赖于问题规模n，所以该算法的空间复杂度是O(1)，即该算法是“原地工作”的。综合来看，这是一个高效率的算法。

三、数组中特定值元素的删除

        0.题目 : 

        有一个长度为n的顺序表L，要求删除该顺序表中所有值为5的元素。请设计一个算法来实现上述操作，用C语言描述该算法，并且计算出该算法的时间复杂度和空间复杂度。

        1.算法设计思想 : 

        注意，顺序表中删除特定值的元素与链表中有明显区别。如果是在链表中删除指定值的元素，我们只需要修改被删除结点的前一个结点的指针，使其指向被删除结点的后一个结点，就可以在逻辑上删除这个结点，然后只需要调用free函数释放掉它所占用的内存空间即可。但是在顺序表中，由于顺序表是在一片连续的地址空间中，所以当我们逻辑上删除特定值的元素后，必须向前移动后面的元素来填补空缺，使其仍是一个连续的完整的顺序表。

        那么，怎么能够既删除掉指定值的结点，同时又可以把后面的元素往前移动呢？(这么做有最优的时间复杂度)

        我们可以用一个辅助变量count来记录被删除的元素的个数，然后让后面的元素向前移动count个单位，最后让数组的长度减少count。比方说，一个数组仅有5个元素，分别是{1，2，5，5，3};，在for循环中，如果当前元素的值等于5，我们就让count的值自增1，这样在遍历到第5个元素3时，count已经是2了，这时让元素3向前移动2个单位，同时让数组长度减2，刚好得到我们想要的数组{1，2，3}。

        2.C语言描述 : 

                完整代码如下：(注意看注释) 

# include <stdio.h>
# include <stdlib.h># define MAX_SIZE 100//定义数据结构
typedef struct SqList {int data[MAX_SIZE];int length;int capacity;
} SqList;//函数声明
void initialize(SqList * L);
int deleteByValue(SqList * L, int e);int main(void) {SqList array;initialize(&array);//给出一个具体的顺序表，用于测试该算法int array_demo[] = {1, 5, 11, 5, 80, 5, 5, 141};for (int i = 0; i < 8; ++i) array.data[i] = array_demo[i];array.length = 8;int count = deleteByValue(&array, 5);printf("数组中被删除的值为5的结点一共有%d个~\n",count);printf("删除值为5的元素后, 数组为:");for (int i = 0; i < array.length; ++i) printf("%d ",array.data[i]);return 0;
}void initialize(SqList * L) {L->length = 0;L->capacity = MAX_SIZE;
}int deleteByValue(SqList * L, int e) {if (L == NULL || L->length == 0) {return -1;}int count = 0;                              //count变量用来记录被删除的结点的个数for (int i = 0; i < L->length; ++i) {if (L->data[i] == e) {                   //每遇到一个值为e的元素，就对count进行自增count++;} else {                                //如果当前元素的值不为e，就向前移动count个单位L->data[i - count] = L->data[i];}}L->length = L->length - count;              //最后别忘记更新数组的长度return count;
}

                运行结果 : 

        3.算法的时间和空间复杂度 : 

        (1) 时间复杂度 : 

        在deleteByValue方法中，我们只遍历了一次顺序表，for循环内语句的执行次数与问题规模n成正比例关系，所以时间复杂度为O(n)。
        (2) 空间复杂度 : 

        只使用了几个辅助变量，所以空间复杂度为O(1)，即该算法是“原地工作”的。综合来看，这是一个解决该类问题的最佳算法。

四、数组中值位于某一区间的元素的删除

        0.题目 : 

        现有一顺序表，要求删除顺序表中所有值位于[a,b]区间的元素（a < b），若区间表示范围不合理或顺序表为空，则显示出错误信息并退出运行。请设计一个算法来实现上述操作，用C语言描述该算法，并且计算出该算法的时间复杂度和空间复杂度。

        1.算法设计思想 : 

        同上文中“数组中特定值元素的删除”类似，我们可以用一个辅助变量count来记录被删除的元素的个数，然后让后面的元素向前移动count个单位，最后让数组的长度减少count。然后我们只需要修改一下if条件语句的判断条件就行。

        2.C语言描述 : 

                完整代码如下：(注意看注释)  

# include <stdio.h>
# include <stdlib.h># define MAX_SIZE 100//定义数据结构
typedef struct SqList {int data[MAX_SIZE];int length;int capacity;
} SqList;//函数声明
void initialize(SqList * array);
int deleteByRange(SqList * array, int a, int b); int main(void) {SqList array;initialize(&array);//给出一个具体的顺序表，用于测试该算法(测试删除值位于[3.5]区间的元素)int array_demo[] = {1, 2, 3, 4, 4, 5, 5, 11, 999, 11, 5};for (int i = 0; i < 11; ++i) array.data[i] = array_demo[i];array.length = 11;int count = deleteByRange(&array, 3, 5);printf("数组中一共被删掉了%d个元素\n", count);printf("删除值位于[3,5]的元素后，数组剩余元素如下：\n");for (int i = 0; i < array.length; ++i) printf("%d ",array.data[i]);return 0;
}void initialize(SqList * array) {array->length = 0;array->capacity = MAX_SIZE;
}int deleteByRange(SqList * array, int a, int b) {if (a > b) {printf("请输入正确的区间~");exit(0);return -1;}if (array == NULL || array->length == 0) {printf("请传入合法的数组~");}int count = 0;for (int i = 0; i < array->length; ++i) {if (array->data[i] >= a && array->data[i] <= b) {count++;} else {array->data[i - count] = array->data[i];}}array->length = array->length - count;return count;
}

                运行结果 ：

        3.算法的时间和空间复杂度 : 

        (1) 时间复杂度 : 

        在deleteByRange方法中，我们只遍历了一次顺序表，for循环内语句的执行次数与问题规模n成正比例关系，所以时间复杂度为O(n)。
        (2) 空间复杂度 : 

        只使用了几个辅助变量，所以空间复杂度为O(1)，即该算法是“原地工作”的。综合来看，这是一个解决该类问题的最佳算法。

五、数组的去重

        0.题目 : 

        已知某有序表中存在值重复的元素，要求从中删除所有值重复的元素，使表中所有元素的值均不相同。请设计一个算法来实现上述操作，用C语言描述该算法，并且计算出该算法的时间复杂度和空间复杂度。

        1.算法设计思想 : 

        首先注意这个算法的前提——有序表。显然，如果要对一个有序表去重，那么有序表中自然而然就有两种元素——具有重复值的元素和不重复的元素。类似于上文“数组中特定值元素的删除” 和 “数组中值位于某一区间的元素的删除”，我们只要用不重复的元素覆盖掉重复的元素，就可以在逻辑上完成有序顺序表的去重。当然我们希望在一次遍历过程就完成这件事，这样可以达到O(n)的时间复杂度，这是这类问题的最优时间复杂度。

        那么，我们怎么利用代码来实现呢？

        我们可以使用两个辅助变量uniqueIndex和currentIndex，这是两个循环变量，也是两个下标，其中uniqueIndex用于指向已经保存的元素，它的初始值是0；而currentIndex表示当前指向的元素，也就是需要进行比较的第一个元素，它的初始值是1，因为当下标指向数组的第一个元素时，第一个元素一定不会重复，它前面已经没有其他元素了，所以第一个元素不需要进行比较。比较这两个下标指向的元素，如果当前指向的元素和已经保存的元素不相同，说明当前元素也需要被保存，这时，要先移动uniqueIndex指针(++uniqueIndex)，再进行元素的覆盖(array->data[++uniqueIndex] = array->data[currentIndex];)。如果相同，说明当前指向的元素是重复的，不需要进行操作，直接进行下一次循环即可。

        2.C语言描述 : 

                完整代码如下：(注意看注释)  

# include <stdio.h>
# include <stdlib.h># define MAX_SIZE 100//定义数据结构
typedef struct SqList {int data[MAX_SIZE];int length;int capacity;
} SqList;//函数声明
void initialize(SqList * array);
int removeDuplicates(SqList * array);int main(void) {SqList array;initialize(&array);//给出一个具体的有序表，用于测试该算法int array_demo[] = {1, 2, 2, 3, 4, 5, 5, 5, 11, 19, 23, 23, 55, 141};for (int i = 0; i < 14; ++i) array.data[i] = array_demo[i];array.length = 14;int count = removeDuplicates(&array);printf("被删除的重复元素一共有%d个\n",count);printf("去重后的有序表如下——\n");for (int i = 0; i < array.length; ++i) printf("%d ",array.data[i]);return 0;
}void initialize(SqList * array) { array->length = 0;array->capacity = MAX_SIZE;
}int removeDuplicates(SqList * array) {if (array->length == 0 || array == NULL) return -1;int count = 0;      //count变量用于记录被删除的元素的个数。/*(1) uniqueIndex下标记录已经保存的元素;currentIndex下标记录当前指向的元素。(2) uniqueIndex初始值为0，指向数组第一个元素;currentIndex初始值为1，指向数组第二个元素。*/for (int uniqueIndex = 0,currentIndex = 1; currentIndex < array->length; ++currentIndex) { /*如果当前指向的元素和已经保存的元素不相同，(注意现在是一个有序表)则当前元素也需要保存，uniqueIndex下标和currentIndex下标都会向右移动；否则不保存当前元素，只移动currentIndex下标。   */if (array->data[currentIndex] != array->data[uniqueIndex]) {array->data[++uniqueIndex] = array->data[currentIndex];      //先移动下标，后覆盖元素。} else {count++;}}array->length = array->length - count;return count;
}

                运行结果 : 

        3.算法的时间和空间复杂度 : 

        (1) 时间复杂度 : 

        一次遍历就实现了有序表的去重，所以该算法的时间复杂度是O(n)。
        (2) 空间复杂度 : 

        只使用了几个临时的辅助变量，所以该算法的空间复杂度是O(1)。也就是说该算法是“原地工作”的，显然这是解决该类问题最优的算法。

六、数组中两个子数组的位置互换

        0.题目 : 

        已知在一个一维数组A[m+n]中，依次存放有两个顺序表(a1, a2, ..., am) 和 (b1, b2, ..., bn)，现在要求将这两个顺序表的位置进行互换，即将(b1, b2, ..., bn) 放在 (a1, a2, ..., am)的前面。请设计一个算法来实现上述操作，用C语言描述该算法，并且计算出该算法的时间复杂度和空间复杂度。

        1.算法设计思想 : 

        就是把{a1,a2,...,am,b1,b2,...,bn} 变成 {b1,b2,...,bn,a1,a2,...,am}，也就是说两个子数组的顺序换了，但是子数组内部依然保持着原来的顺序。我们要将这个题目和上文“数组元素的倒置”联系起来。如果一开始的数组是{am,..a2,a1,bn,...,b2,b1}，那么我们是不是只需要将这个数组倒置一次就变成了我们想要的数组。但是怎么才能利用这个过渡的数组来完成算法呢？先将两个子数组分别倒置，再将整个数组进行一次倒置，就可以得到我们最终想要的数组。

        那么，代码怎么实现？

        可知我们一共需要进行三次“倒置”，前两次是分别将两个子数组倒置，后一次是直接将整个数组进行倒置。所以我们可以利用上文中“数组元素的倒置”的算法，通过调整传入的形参，调用三次该算法，即可成功互换两个子数组的位置。

        2.C语言描述 : 

                完整代码如下：(注意看注释)  

# include <stdio.h>
# include <stdlib.h># define MAX_SIZE 100//定义数据结构
typedef struct SqList {int data[MAX_SIZE];int length;int capacity;
} SqList;//函数声明
void initialize(SqList * array);
void reverse(SqList * array, int start, int end);
void reverseTwoSubArray(SqList * array, int formerLength, int latterLength);int main(void) {SqList array;initialize(&array);//给出一个具体的顺序表，用于测试该算法int array_demo[] = {11, 12, 13, 14, 15, 1, 2, 3, 4, 5, 6, 7};for (int i = 0; i < 12; ++i) array.data[i] = array_demo[i];array.length = 12;printf("逆置两个子数组前，整个数组的情况如下———\n");for (int i = 0; i < 12; ++i) printf("%d ", array.data[i]);reverseTwoSubArray(&array, 5, 7);printf("\n逆置两个子数组后，整个数组的情况如下————\n");for (int i = 0; i < 12; ++i) printf("%d ", array.data[i]);return 0;
}/**function : initialize(as its name)parameter list : array---the arraylist which you want to initialize*/
void initialize(SqList * array) {array->length = 0;array->capacity = MAX_SIZE;
}/**fucntion : reverse(just a certain part of an array)parameter list : (1)array---operated arraylist;(2)start---the index of the opening element of the array;(3)end---the index of the ending element of the array;*/
void reverse(SqList * array, int start, int end) {int temp = 0;int subArrayLength = end - start;for (int i = 0; i < subArrayLength / 2; ++i) {temp = array->data[start];array->data[start] = array->data[end - i];array->data[end - i] = temp;start++;}
}/**function : reverseTwoSubArray(which will invoke the reverse function above)parameter list : (1)array---operated arraylist;(2)formerLength---the former subarray's length, logically;(3)latterLength---the latter subarray's length, also logically;*/
void reverseTwoSubArray(SqList * array, int formerLength, int latterLength) {if ((formerLength + latterLength) != array->length) {printf("请输入合法的子数组长度~\n");exit(0);}reverse(array, 0, formerLength - 1);                                  //先转置前m个元素reverse(array, formerLength, formerLength + latterLength - 1);        //后转置后n个元素reverse(array, 0, formerLength + latterLength - 1);                   //最后转置整个数组
}

        3.算法的时间和空间复杂度 : 

        (1) 时间复杂度 : 

        Let's break down the operations in the reverseTwoSubArray function:

        The first reverse call operates on the first subarray of length formerLength.
        The second reverse call operates on the second subarray of length latterLength.
        The third reverse call operates on the entire array of length n (where n = formerLength + latterLength).
        Let's look at the reverse function:

        It performs swaps for half the length of the subarray it's operating on.
        So, the total number of operations is:

        formerLength/2 (first reverse)
        latterLength/2 (second reverse)
        n/2 (third reverse, where n = formerLength + latterLength)
        Adding these up: formerLength/2 + latterLength/2 + n/2 = n/2 + n/2 = n

        Therefore, the total number of operations is proportional to n, giving us O(n) time complexity.

        (2) 空间复杂度 : 

        The space complexity is O(1) (constant space) because:

        We're not using any additional data structures that grow with the input size.
        We're performing the reversal in-place, meaning we're only using a fixed amount of extra space regardless of the input size.
        The only extra space used is for a few variables (like temp in the reverse function), which doesn't change regardless of the array size.
        Even if the input array is very large, we don't need any more memory than these few variables. This is why we say the space complexity is constant, or O(1).

七、数组元素的循环移动 [2010真题]

        0.题目 : 

        设将n(n>1)个整数存放到一维数组R中，设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0<p<n)个位置，即将R中的数据由(X0,X1,.Xn-1)变换为(Xp,Xp+1,...,Xn-1,X0,X1,...Xp-1)。要求：

        1）给出算法的基本设计思想。

        2）根据设计思想，采用C语言描述算法，关键之处给出注释。

        3）说明你所设计算法的时间复杂度和空间复杂度。

        1.算法设计思想 :

        本质和上一题“数组中两个子数组的位置互换”一样，我们可以将一维数组R在逻辑上分为两个子数组，第一个数组就是循环左移的那p个元素构成的数组，即X0~Xp-1；第二个数组就剩剩余的那n-p个元素构成的数组。所以这道题目可以转化为——在一维数组R中包含两个顺序表，把含有p个元素和n-p个元素的两个顺序表互换位置。

        所以，算法的设计思想——先将前p个元素逆置，再将后面n-p个元素逆置，最后将整个数组进行一次倒置，就可以得到我们最终想要的数组。即，先将{X0,X1,...,Xp-1,Xp,Xp+1,...Xn-1}变成{Xp-1,...X1,X0,Xn-1,...,Xp+1,Xp}，然后再将它整体逆置，变成{Xp,Xp+1,...Xn-1,X0,X1,...,Xp-1}，达到的最终效果就是整个一维数组R循环左移了p个位置。

        2.C语言描述 : 

                完整代码如下：(注意看注释)  

# include <stdio.h>
# include <stdlib.h># define MAX_SIZE 100//定义数据结构
typedef struct SqList {int data[MAX_SIZE];int length;int capacity;
} SqList;//函数声明
void initialize(SqList * array);
void reverse(SqList * array, int start, int end);
void loopMoveLeft(SqList * array, int p);int main(void) {SqList R;initialize(&R);//给出一个具体的顺序表，用于测试该算法。int array_R[] = {11, 13, 15, 12, 11, 11, 1, 2, 3, 4, 5};for (int i = 0; i < 11; ++i) R.data[i] = array_R[i];R.length = 11;printf("循环左移前的数组长这样儿——\n");for (int i = 0; i < R.length; ++i) printf("%d ", R.data[i]);loopMoveLeft(&R, 6);    //假设循环左移6个元素printf("\n循环左移后的数组长这样儿——\n");for (int i = 0; i < R.length; ++i) printf("%d ", R.data[i]);return 0;
}/**function : initialize(as its name)parameter list : (1) array : the operated array*/
void initialize(SqList * array) {array->length = 0;array->capacity = MAX_SIZE;
}/**function : reverse(just a certain part of an array)parameter list : (1)array---operated arraylist;(2)start---the index of the opening element of the subarray;(3)end---the index of the ending element of the subarray;*/
void reverse(SqList * array, int startIndex, int endIndex) {int temp = 0;int subArrayLength = endIndex - startIndex;for (int i = 0; i < subArrayLength / 2; ++i) {temp = array->data[startIndex];array->data[startIndex] = array->data[endIndex - i];array->data[endIndex - i] = temp;startIndex++;}
}/**function : loop move left p elements of an arraylistparameter list : (1) array---which array you want to cope with(2) p---the number of elements which will be loop move left
*/
void loopMoveLeft(SqList * array, int p) {if (array == NULL) {printf("请传入合法的数组~\n");exit(0);}if (array->length == 0) {printf("数组为空~\n");exit(0);}   // Handle cases where p is larger than array lengthp = p % array->length;if (p == 0) return;  // No movement neededreverse(array, 0, p-1);                           //先逆置前p个元素reverse(array, p, array->length - 1);             //再逆置后n-p个元素reverse(array, 0, array->length - 1);             //最后逆置整个数组
}

                运行结果 : 

        3.算法的时间和空间复杂度 : 

        (1) 时间复杂度 : 

        p/2 + (n-p)/2 + n/2 = n，所以时间复杂度为O(n)。（更详细地说明见上一题）

        (2) 空间复杂度 : 

        只使用了几个辅助变量，所以空间复杂度为O(1)。（更详细地说明见上一题）

Δ总结

  • up会根据数组--->链表--->二叉树--->图，这么一个顺序来分享408算法题的解题思路和方法。
  • 这篇博文写得不长，一共也就七道题，而且这七道题难度都不高，但是以“数组”作为算法题的入门再合适不过了；况且这七道题目之间也有紧密的联系，比方说第二题“数组元素的倒置”就是第六题和第七题的基础，而第七题又借鉴了第六题的思路。
  • 🆗，以上就是这篇博文的全部内容了，感谢阅读！

        System.out.println("END--------------------------------------------------");

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/402444.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

SpringBoot3 + Flowable7 工作流引擎使用笔记

SpringBoot3 + Flowable7 工作流引擎使用笔记

目录 Flowable 简介流程设计器安装使用 SpringBoot 3 整合表结构流程部署启动流程流程审批流程挂起和激活任务分配固定分配表达式分配值表达式方法表达式 监听器分配 流程变量运行时变量历史变量 身份服务候选人拾取任务归还任务指派给别人候选人组创建用户创建用户组用户关联用…
阅读更多...
VueUse 基于 Vue 3 Composition API 的高质量 Hooks 库

VueUse 基于 Vue 3 Composition API 的高质量 Hooks 库

VueUse 是什么？ VueUse 是基于 Vue 3 Composition API 的高质量 Hooks 库。例如获取滚动的距离 VueUse 官网：VueUse | VueUse VueUse 什么使用？ 1、通过npm安装 VueUse npm i @vueuse/core 2、搜索需要使用的函数，例如搜索 useScroll 滚动 3、使用useScroll 滚动函数 …
阅读更多...
C语言传递指针给函数

C语言传递指针给函数

C 语言允许您传递指针给函数&#xff0c;只需要简单地声明函数参数为指针类型即可。 下面的实例中&#xff0c;我们传递一个无符号的 long 型指针给函数&#xff0c;并在函数内改变这个值 实例1&#xff1a;获取系统的时间值 能接受指针作为参数的函数&#xff0c;也能接受数…
阅读更多...
为什么Pandas是最流行的Python数据分析库？

为什么Pandas是最流行的Python数据分析库？

本文将从Python生态、Pandas历史背景、Pandas核心语法、Pandas学习资源四个方面去聊一聊Pandas&#xff0c;期望能带给大家一点启发。 一、Python生态里的Pandas 五月份TIOBE编程语言排行榜&#xff0c;Python追上Java又回到第二的位置。Python如此受欢迎一方面得益于它崇尚简…
阅读更多...
零成本 API 服务搭建，用 GitHub Actions 自动爬取文章？

零成本 API 服务搭建，用 GitHub Actions 自动爬取文章？

前言 本着将成本降到最低&#xff0c;我目前做的应用或小程序都是单机的&#xff0c;也就是不用请求接口&#xff0c;只要一上架就没有任何支出。但是写死的数据毕竟有限&#xff0c;应用的内容单一无法紧跟时事热点&#xff0c;每次打开一个样&#xff0c;自然就没有留存。遇…
阅读更多...
Redis13-多级缓存

Redis13-多级缓存

目录 概述 JVM进程缓存 Caffeine 实现进程缓存 Lua语法 初识Lua 变量和循环 Lua的数据类型 声明变量 循环 条件控制、函数 函数 条件控制 实现多级缓存 安装OpenResty OpenResty快速入门 请求参数处理 查询Tomcat 发送http请求的API 封装http工具 CJSON工…
阅读更多...
CSS小玩意儿：文字适配背景

CSS小玩意儿：文字适配背景

一&#xff0c;效果 二&#xff0c;代码 1&#xff0c;搭个框架 添加一张背景图片&#xff0c;在图片中显示一行文字。 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" conte…
阅读更多...
【Python】高效的Web自动化测试利器—Python+Playwright快速上手自动化实战指南（限时开放）

【Python】高效的Web自动化测试利器—Python+Playwright快速上手自动化实战指南（限时开放）

文章目录 前言一.playwright是什么二.python引入playwright1.安装2.playwright命令行参数3.playwright codegen自动生成代码4.Chrome和Chromium有什么关系&#xff1f; 三.基本概念1. 无头浏览器&#xff08;Headless Browser&#xff09;2.同步和异步模式操作playwright2.1.同…
阅读更多...
SQL每日一练-0815

SQL每日一练-0815

今日SQL题难度&#xff1a;&#x1f31f;☆☆☆☆☆☆☆☆☆ 1、题目要求 计算每个产品类别在每个月的总销售额和总销量。找出每个月销售额最高的产品类别&#xff0c;显示类别名称、销售月份、总销售额和总销量。 2、表和虚拟数据 现有两个表&#xff1a;Products 和…
阅读更多...
RockerMQ学习

RockerMQ学习

消息中间件以前常用RabbitMQ和ActiveMQ&#xff0c;由于业务需要&#xff0c;后期业务偏向大数据&#xff0c;现着重学习一下RocketMQ&#xff08;RocketqMQ原理同ctg-mq&#xff09;&#xff0c;后续更新Kafka 一、RocketMQ特性 Kafka特性 &#xff08;高性能分布式&#xff…
阅读更多...
day34-nginx常用模块

day34-nginx常用模块

## 0. 网络面试题 网络面试题: TCP三次握手 TCP四次挥手 DNS解析流程 OSI七层模型 抓包工具 tcpdump RAID级别区别 开机启动流程 如何实现不同的网段之间通信(路由器) ip route add 192.168.1.0 255.255.255.0 下一跳的地址或者接口 探测服务器开启了哪些端口(无法登录服务器…
阅读更多...
渗透测试-行业术语

渗透测试-行业术语

1.肉鸡 肉鸡用来比喻哪些可以随意被我们控制的计算机&#xff0c;可以是普通的个人电脑&#xff0c;也可以是大型服务器或者其他网络设备&#xff0c;我们可以像操作自己的电脑一样操作他们而不被发觉。 2.木马 表面上伪装成了正常程序&#xff0c;但是当程序被运行的时候&a…
阅读更多...
配置MySQL主从，配置MySQL主主 +keeplive高可用

配置MySQL主从，配置MySQL主主 +keeplive高可用

在大数据-Hadoop体系中 配置MySQL主主keeplive高可用 注意&#xff1a;这个是我两年前的word文档&#xff0c;可以当作参考文档有个思路参考一下&#xff0c;但是里面可能有些地方有误 另外 :关于一些企业级实战技术可以参考这篇mysql 物理备份 MySQL 全量备份 增量备份 差异…
阅读更多...
Linux_vi vim的使用

Linux_vi vim的使用

目录 vi和vim的基本介绍 vi和vim常用的三种模式 案例演示 vim的快捷键 快捷键使用练习 vi和vim的基本介绍 linux系统内会内置vi文本编译器。vim可以简单认为是vi的增强版本。 vi和vim常用的三种模式 有正常模式&#xff0c;移动光标&#xff0c;删除字符等。插入模式可以进…
阅读更多...
Flask 线上高并发部署方案实现

Flask 线上高并发部署方案实现

目录 1、Flask默认多线程执行 2、使用gevent.pywsgi实现 3、是用uWSGI服务器实现 1、Flask默认多线程执行 前言&#xff1a;在Flask的较早版本中&#xff0c;默认并不支持多线程模式。然而&#xff0c;从Flask 0.9版本开始&#xff0c;引入了多线程模式的支持&#xff0c;并…
阅读更多...
【自动驾驶】ROS中的TF坐标变换（一）：静态坐标变换

【自动驾驶】ROS中的TF坐标变换（一）：静态坐标变换

目录 引子ros中的右手坐标系补充&#xff1a;欧拉角及四元数理解旋转平移操作复合操作 运行坐标变换的例子坐标转换 静态坐标变换-发布坐标系信息创建功能包 静态坐标变换-订阅坐标系信息添加cpp订阅者主文件修改cmakelist文件编译报错的解决方案运行程序进行测试 引子 机器人…
阅读更多...
【MySQL数据库】单机、集群、分布式的区别

【MySQL数据库】单机、集群、分布式的区别

单机、集群和分布式是计算机系统中三种不同的架构模型，它们在资源管理、任务执行和性能优化方面有显著区别。 图片来源 1. 单机（Standalone） 单机指的是单一计算机系统，即所有的计算任务和数据都在一台计算机上处理。单机系统的特点包括： 硬件限制：受限于单台机器的计…
阅读更多...
Visual Studio 2022 无法打开源文件atlimage.h

Visual Studio 2022 无法打开源文件atlimage.h

最近在搞tcp socket 通信demo&#xff0c;网上抄了一下源码&#xff08;代码参考&#xff1a;C中的Socket编程使用协议发送图片_快速传输 照片 c-CSDN博客&#xff09;&#xff0c;还没开始编译就提示 无法打开源文件atlimage.h&#xff0c;全局搜了一下没有这个文件&#xff0…
阅读更多...
JSON Web Token (JWT): 理解与应用

JSON Web Token (JWT): 理解与应用

JWT&#xff08;JSON Web Token&#xff09;是一种开放标准&#xff08;RFC 7519&#xff09;&#xff0c;它定义了一种紧凑且自包含的方式&#xff0c;用于在各方之间以JSON对象的形式安全地传输信息。JWT通常用于身份验证和授权目的&#xff0c;因为它可以使用JSON对象在各方…
阅读更多...
Unity开发抖音小游戏广告部分接入

Unity开发抖音小游戏广告部分接入

Unity开发抖音小游戏广告部分接入 介绍环境确保开通流量主获取广告位广告部分代码测试如下总结 介绍 最近在使用Unity做抖音小游戏这块的内容&#xff0c;因为要接入广告&#xff0c;所以这里我把我接入广告的部分代码和经验分享一下。 环境确保 根据抖音官方的文档我们是先…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023