AI 助理
备案控制台
开发者社区 人工智能 文章 正文

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

2025-02-02 13
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 408考研——《数据结构》算法题基础篇之数组。(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;
}

image.gif

               运行结果 :

image.gif 编辑

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

image.gif

               运行结果 :

image.gif 编辑

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

image.gif

               运行结果 :

image.gif 编辑

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

image.gif

               运行结果 ：

image.gif 编辑

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

image.gif

               运行结果 :

image.gif 编辑

       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 + 1;   
    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);                   //最后转置整个数组
}

image.gif

               运行结果 :

image.gif 编辑

       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 + 1;
    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 arraylist
    parameter 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 length
    p = p % array->length;
    if (p == 0) return;  // No movement needed
    reverse(array, 0, p-1);                           //先逆置前p个元素
    reverse(array, p, array->length - 1);             //再逆置后n-p个元素
    reverse(array, 0, array->length - 1);             //最后逆置整个数组
}

image.gif

              运行结果 :

image.gif 编辑

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

       (1) 时间复杂度 :

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

       (2) 空间复杂度 :

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

Δ总结

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

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

文章标签：
算法
C语言
人工智能
存储
Cyan_RA9
目录
相关文章
云安全专家
|
27天前
|
供应链 监控 安全
对话｜企业如何构建更完善的容器供应链安全防护体系
阿里云与企业共筑容器供应链安全
云安全专家
171358 14
弹性计算-百晓生
|
30天前
|
供应链 监控 安全
对话｜企业如何构建更完善的容器供应链安全防护体系
随着云计算和DevOps的兴起，容器技术和自动化在软件开发中扮演着愈发重要的角色，但也带来了新的安全挑战。阿里云针对这些挑战，组织了一场关于云上安全的深度访谈，邀请了内部专家穆寰、匡大虎和黄竹刚，深入探讨了容器安全与软件供应链安全的关系，分析了当前的安全隐患及应对策略，并介绍了阿里云提供的安全解决方案，包括容器镜像服务ACR、容器服务ACK、网格服务ASM等，旨在帮助企业构建涵盖整个软件开发生命周期的安全防护体系。通过加强基础设施安全性、技术创新以及倡导协同安全理念，阿里云致力于与客户共同建设更加安全可靠的软件供应链环境。
弹性计算-百晓生
150302 32
弹性计算-百晓生
|
2月前
|
弹性计算 人工智能 安全
对话 | ECS如何构筑企业上云的第一道安全防线
随着中小企业加速上云，数据泄露、网络攻击等安全威胁日益严重。阿里云推出深度访谈栏目，汇聚产品技术专家，探讨云上安全问题及应对策略。首期节目聚焦ECS安全性，提出三道防线：数据安全、网络安全和身份认证与权限管理，确保用户在云端的数据主权和业务稳定。此外，阿里云还推出了“ECS 99套餐”，以高性价比提供全面的安全保障，帮助中小企业安全上云。
弹性计算-百晓生
201980 15
对话 | ECS如何构筑企业上云的第一道安全防线
coder一枚
|
4天前
|
Linux iOS开发 MacOS
deepseek部署的详细步骤和方法，基于Ollama获取顶级推理能力！
DeepSeek基于Ollama部署教程，助你免费获取顶级推理能力。首先访问ollama.com下载并安装适用于macOS、Linux或Windows的Ollama版本。运行Ollama后，在官网搜索“deepseek”，选择适合你电脑配置的模型大小（如1.5b、7b等）。通过终端命令（如ollama run deepseek-r1:1.5b）启动模型，等待下载完成即可开始使用。退出模型时输入/bye。详细步骤如下图所示，轻松打造你的最强大脑。
coder一枚
2001 74
魔搭ModelScope社区小助手
|
11天前
|
机器学习/深度学习 自然语言处理
Deepseek开源R1系列模型，纯RL助力推理能力大跃升！
近期Deepseek正式发布 DeepSeek-R1，并同步开源模型权重。DeepSeek-R1 遵循 MIT License，允许用户通过蒸馏技术借助 R1 训练其他模型。
魔搭ModelScope社区小助手
1145 24
唠唠低代码
|
7天前
|
人工智能 JavaScript 前端开发
白嫖 DeepSeek ，低代码竟然会一键作诗？
宜搭低代码平台接入 DeepSeek AI 大模型能力竟然这么方便！本教程将揭秘宜搭如何快速接入 DeepSeek API，3 步打造专属作诗机器人，也许你还能开发出更多有意思的智能玩法，让创意在代码间自由生长。
唠唠低代码
679 11
云服务器小助手
|
5天前
|
Linux iOS开发 MacOS
DeepSeek爆火，如何免费部署到你的电脑上？获取顶级推理能力教程来了
如何在本地电脑上免费部署DeepSeek，获取顶级推理能力？只需三步：1. 访问Ollama官网下载并安装对应操作系统的版本（支持macOS、Linux和Windows）。2. 打开Ollama并确保其正常运行。3. 在Ollama官网搜索并选择DeepSeek模型（如deepseek-r1），根据电脑配置选择合适的模型大小（1.5B至671B）。通过终端命令（如ollama run deepseek-r1:1.5b）运行模型，即可开始使用DeepSeek进行推理。退出模型时，在终端输入/bye。更多详情请参考Ollama官方文档。
云服务器小助手
2074 33
云上的喵酱
|
3天前
|
网络协议 应用服务中间件 网络安全
Nginx，正向代理
本文介绍了Nginx作为HTTPS正向代理的两种方案：HTTP CONNECT隧道（7层）和NGINX stream（4层）。HTTP CONNECT隧道需要客户端手动配置代理，通过CONNECT请求建立隧道；而NGINX stream则更适合透明代理，利用SNI字段实现流量转发。文章详细讲解了两者的原理、环境搭建、使用场景及常见问题，并提供了配置示例和最佳实践建议。内容转载自阿里云开发者社区@怀知的文章，推荐读者参阅原文获取更多信息。感谢您的阅读！
云上的喵酱
184 78
Nginx，正向代理
周周的奇妙编程
|
16天前
|
机器学习/深度学习 自然语言处理 PyTorch
深入剖析Transformer架构中的多头注意力机制
多头注意力机制（Multi-Head Attention）是Transformer模型中的核心组件，通过并行运行多个独立的注意力机制，捕捉输入序列中不同子空间的语义关联。每个“头”独立处理Query、Key和Value矩阵，经过缩放点积注意力运算后，所有头的输出被拼接并通过线性层融合，最终生成更全面的表示。多头注意力不仅增强了模型对复杂依赖关系的理解，还在自然语言处理任务如机器翻译和阅读理解中表现出色。通过多头自注意力机制，模型在同一序列内部进行多角度的注意力计算，进一步提升了表达能力和泛化性能。
周周的奇妙编程
862 47
小华同学ai
|
3天前
|
资源调度 JavaScript 前端开发
Van-Nav：新年，将自己学习的项目地址统一整理搭建自己的私人导航站，供自己后续查阅使用，做技术的同学应该都有一个自己网站的梦想
嗨，大家好，我是小华同学。今天为大家介绍一个基于Vue.js开发的导航组件库——Van-Nav。它支持响应式设计、多级菜单、丰富的配置选项和多种动画效果，适用于企业官网、电商平台、内容管理系统和个人博客等多种场景。轻松集成到Vue项目中，提供清晰有序的导航体验。关注我们获取更多优质开源项目和高效工作学习方法。
小华同学ai
156 68