数据结构c语言版：顺序表oj题练习（原地移除元素、合并两个有序数组）-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构c语言版：顺序表oj题练习（原地移除元素、合并两个有序数组）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

原地移除元素

题目：来源力扣。

数据结构c语言版：顺序表oj题练习（原地移除元素、合并两个有序数组）,数据结构,数据结构,c语言,开发语言

思路1

在单数组里面历遍找val，如果是val，就删除。不是就跳过。

时间复杂度O（n^2),最坏情况每个都是val。相当于一个等差数列。

比如

输入：nums = [0,1,2,2,3,0,4,2], val = 2

下标0开始找，0不是，不动数组
下标1，1不是，不动数组
下标2，2是，删除元素，变成【0，1，2，3，0，4，2】
下标2，2是，删除元素，变成【0，1，3，0，4，2】
下标2，3不是，不动数组
下标3，0不是，不动数组
下标4，4不是，不动数组
下标5，5是，删除元素，变成【0，1，3，0，4】

#include <stdio.h>

int removeElement(int nums[], int length, int val) 
{
    // 初始化计数器
    int count = 0;

    // 遍历数组
    for (int i = 0; i < length; i++) 
    {
        // 如果当前元素不等于 val
        if (nums[i] != val) 
        {
            // 将当前元素移到数组的正确位置
            nums[count] = nums[i];
            // 更新计数器
            count++;
        }
    }

    // 返回新长度
    return count;
}

int main() 
{
    // 示例用法
    int nums[] = {3, 2, 2, 3, 4, 5, 6};
    int length = sizeof(nums) / sizeof(nums[0]);  // 计算数组长度
    int val = 3;

    // 调用移除元素的函数
    int newLength = removeElement(nums, length, val);

    // 打印移除后的数组元素
    for (int i = 0; i < newLength; i++) 
    {
        printf("%d ", nums[i]);
    }

    return 0;
}

思路2

以空间换时间，时间复杂度O(n),空间复杂度O(n)。

新开辟一块空间，将不是val的值储存到新空间中。重新统计新数组的元素个数。

这里不做代码展示。

思路3

双指针，用src(用来判断元素是不是val)和dst(保存不是val的元素)。

1。不是val，src++，dst++。

2.是val，src++。

时间复杂度O(n),时间复杂度O(1)。

例子

输入：nums = [0,1,2,2,3,0,4,2], val = 2

下标0，0不是，src++到下标1，dst++，记录dst++为src下标0：0。

下标1，1不是，src++到下标2，dst++，记录dst++为src下标1：1。

下标2，2是，src++到下标3，dst不变。

下标3，2是，src++到下标4，dst不变。

下标4，3不是，src++到下标5，dst++，记录dst++为src下标4：3。

下标5，0不是，src++到下标6，dst++，记录dst++为src下标5：0。

下标6，4不是，src++到下标7，dst++，记录dst++为src下标6：4。

下标7，2是，src++，历遍完全部数组，结束。

此时，dst的数组值为【0，1，3，0，4】，dst移动4次，包括开始的，5个数。

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

合并两个有序数组

题目：来源力扣。

数据结构c语言版：顺序表oj题练习（原地移除元素、合并两个有序数组）,数据结构,数据结构,c语言,开发语言

思路

为避免0的影响，两个数组选最大的依次排序，从大到小排序，将最大的排在最后面，以此类推至最前面。

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{
    int end1=m-1;
    int end2=n-1;
    int end=m+n-1;
    while(end1>=0  &&  end2>=0)//都没有结束
    {
        if(nums1[end1]>nums2[end2])
        {
            nums1[end]= nums1[end1];
            --end;
            --end1;
        }
        else
        {
            nums1[end]=nums2[end2];
            --end;
            --end2;
        }
    }
     while(end2>=0)
     {
         nums1[end]=nums2[end2];
         --end;
         --end2;
     }
}

首先，初始化三个指针 end1、end2 和 end，分别指向 nums1、nums2 和合并后的数组的末尾。
进入循环，条件是两个数组都还没有遍历完成。在循环中，比较 nums1 和 nums2 中指针位置的元素大小：
- 如果 nums1[end1] 大于 nums2[end2]，将 nums1[end1] 复制到合并后的数组的末尾，并分别减小 end 和 end1 的值。
- 否则，将 nums2[end2] 复制到合并后的数组的末尾，并分别减小 end 和 end2 的值。
如果第一个数组 nums1 还有剩余元素未遍历，而第二个数组 nums2 已经遍历完了，那么将剩余的 nums1 元素复制到合并后的数组中。文章来源地址https://www.toymoban.com/news/detail-816919.html