数据结构初阶：详解顺序表OJ题

用户11831438

发布于 2025-12-30 12:22:32

1120

🔥个人主页：胡萝卜3.0 🎬作者简介：C++研发方向学习者 📖个人专栏： 《C语言》《数据结构》 《C++干货分享》 ⭐️人生格言：不试试怎么知道自己行不行

一、移除元素

27. 移除元素 - 力扣（LeetCode）

思路1：创建新数组，遍历原数组，将原数组中不为val的元素放入新数组中，遍历完之后，将新数组中的数据拷贝给原数组，最后返回新数组中的数据个数。

将上面的思路转换成代码：

int removeElement(int* nums, int numsSize, int val) {
    int* tmp=(int*)malloc(sizeof(int)*numsSize);
    if(tmp==NULL)
    {
        perror("malloc fail!");
        exit(1);
    }
    //遍历原数组，将不为val的值放入tmp数组中
    int size=0;
    for(int i=0;i<numsSize;i++)
    {
        if(nums[i]!=val)
        {
            tmp[size++]=nums[i];
        }
    }
    //将tmp中的数据导入原数组中
    for(int i=0;i<size;i++)
    {
        nums[i]=tmp[i];
    }
    free(tmp);
    tmp=NULL;
    return size;
}

时间复杂度为：O（N）空间复杂度为：O（N）

上面这个思路的时间复杂度已经很好了，但是空间复杂度不是很好，有没有办法可以降低其空间复杂度，ok，接下来我们看一个比较重要的思路。

思路2：双指针法

定义两个变量des和src，刚开始都指向下标0，遍历数组，src找不为val的值，找到后，arr[des]=arr[src],然后des++,src++；如果src==val，src++

将上面的思路转换成代码：

int removeElement(int* nums, int numsSize, int val) {
    int des=0,src=0;
    while(src<numsSize)
    {
        if(nums[src]!=val)
        {
            nums[des]=nums[src];
            des++;
        }
        src++;
    }
    return des;
}

时间复杂度：O（N）空间复杂度为：O（1）

二、删除有序数组中的重复项

26. 删除有序数组中的重复项 - 力扣（LeetCode）

思路1：

创建一个新数组来存储唯一元素
遍历原数组，将不重复的元素复制到新数组
将新数组的内容复制回原数组的前面部分
返回唯一元素的数量

将上面的思路转换成代码：

int removeDuplicates(int* nums, int numsSize) {
    int* tmp = (int*)malloc(sizeof(int) * numsSize);
    if (tmp == NULL) {
        perror("malloc fail!");
        exit(1);
    }
    // 第一数据肯定是唯一的
    int count = 0;
    tmp[count++] = nums[0];
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] != nums[i - 1]) {
            tmp[count++] = nums[i];
        }
    }
    for (int i = 0; i < count; i++) {
        nums[i] = tmp[i];
    }
    return count;
}

时间复杂度为：O（N）空间复杂度为：O（N）

上面这个思路的时间复杂度已经很好了，但是空间复杂度不是很好，有没有办法可以降低其空间复杂度，ok，接下来我们看一个比较重要的思路。

思路2：双指针

定义两个变量des,src，des=0，src=des+1，遍历数组，src找和des所对应的值不相等的值，找到之后，des++，arr[des]=arr[src]，src++；如果和des所对应的值相等，src++，最终返回des+1

将上面的思路转换成代码：

int removeDuplicates(int* nums, int numsSize) {
    int des=0,src=des+1;
    while(src<numsSize)
    {
        if(nums[src]!=nums[des])
        {
            des++;
            nums[des]=nums[src];
        }
        src++;
    }
    return des+1;
}

时间复杂度：O（N）空间复杂度为：O（1）

三、合并两个有序数组

88. 合并两个有序数组 - 力扣（LeetCode）

思路1：先将这两个数组合并，然后再排序

这个思路过于简单，就不再赘述！！！

思路2：从后往前遍历数组，找大（谁大谁先往后放）

将上面的思路2转换成代码：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int l1=m-1;
    int l2=n-1;
    int l3=m+n-1;
    //遍历两个数组，谁大往后放
    while(l1>=0 && l2>=0)
    {
        if(nums1[l1]>nums2[l2])
        {
            nums1[l3--]=nums1[l1--];
        }
        else
        {
            nums1[l3--]=nums2[l2--];
        }
    }
    //跳出循环
    //如果nums2中的还有数据，需要特殊处理
    while(l2>=0)
    {
        nums1[l3--]=nums2[l2--];
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-12-30，如有侵权请联系 cloudcommunity@tencent.com 删除

数组