数据结构c语言版:顺序表oj题练习(原地移除元素、合并两个有序数组)

发布时间:2024年01月09日

原地移除元素

题目:来源力扣。

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

?

合并两个有序数组

题目:来源力扣。


思路

为避免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;
     }
}
  1. 首先,初始化三个指针?end1end2?和?end,分别指向?nums1nums2?和合并后的数组的末尾。

  2. 进入循环,条件是两个数组都还没有遍历完成。在循环中,比较?nums1?和?nums2?中指针位置的元素大小:

    • 如果?nums1[end1]?大于?nums2[end2],将?nums1[end1]?复制到合并后的数组的末尾,并分别减小?end?和?end1?的值。
    • 否则,将?nums2[end2]?复制到合并后的数组的末尾,并分别减小?end?和?end2?的值。
  3. 如果第一个数组?nums1?还有剩余元素未遍历,而第二个数组?nums2?已经遍历完了,那么将剩余的?nums1?元素复制到合并后的数组中。

文章来源:https://blog.csdn.net/2303_80025768/article/details/135466391
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。