初阶数据结构（C语言实现）——3顺序表和链表（2）

2.3 数组相关面试题

原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。OJ链接
力扣OJ链接-移除元素
删除排序数组中的重复项。力扣OJ链接-删除有序数组中的重复项
合并两个有序数组。力扣OJ链接-合并两个有序数组

2.3.1 移除元素

1. 题目描述

力扣OJ链接-移除元素
原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。
给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。

2. 分析

思路1：另外开辟一个数组，src从头往后遍历，遇到不是要删除元素，就把该元素赋值给数组，直到遍历完整个数组，在最后再把数组赋值到原数组。

思路2：不另外开辟数组就在原数组进行操作
src从前往后遍历，遇到不等于val的数就赋值给dst
然后src++ ，dst++
src遇到val ,不进行赋值，直接src++，dst不变
直到src遍历完整个数组

3. 思路2代码实现

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

在这里插入图片描述

2.3.2 删除重复元素

1. 题目描述

力扣OJ链接-删除有序数组中的重复项
给你一个非严格递增排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与nums 的大小不重要。
返回 k 。

2. 思路

这个和上一道题思路非常类似~重点是要分析，这个判断相等如何设置。
在这里插入图片描述

3. 代码实现

int removeDuplicates(int* nums, int numsSize) {
    int str = 1;
    int end  = 0;
    while(str<numsSize)
    {
        if(nums[str] != nums [end])
        {
           nums[++end] = nums[str++];//这里先++,如果后++，就会覆盖原本的值
        }
        else
        {
            str++;
        }    
    }
    return end+1;
}

进阶写法，虽然代码量更短，但是代码可读性差~

int removeDuplicates(int* nums, int numsSize) {
    int str = 1;
    int end  = 0;
    while(str<numsSize)
    {
        if(nums[str] != nums [end])
           nums[++end] = nums[str++];//这里end必须先++,如果后++，就会覆盖原本的值
        
        str++;
    }    
    return end+1;
}

在这里插入图片描述

2.3.3 合并两个有序数组

1.题目描述

力扣OJ链接-合并两个有序数组
给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

2. 思路

解题思路:
1. 从后往前遍历数组，将nums1和nums2中的元素逐个比较
将较大的元素往nums1末尾进行搬移
2. 第一步结束后，nums2中可能会有数据没有搬移完，将nums2中剩余的元素逐个搬移到nums1
时间复杂度：O(m+n)
空间复杂度: O(1)

两种情况

情况1：

情况2

3. 代码实现

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
 // end1、end2：分别标记nums1 和 nums2最后一个有效元素位置
    // end标记nums1的末尾，因为nums1和nums2中的元素从后往前往nums1中存放
    // ，否则会存在数据覆盖
    int end1 = m-1;
    int end2 = n-1;
    int dst  = m+n-1;//合并后的数组长度是m + n，最后一个元素的位置就是 nums[m+n-1]
    // 从后往前遍历，将num1或者nums2中较大的元素往num1中end位置搬移
    // 直到将num1或者num2中有效元素全部搬移完
    while(end1 >= 0 && end2 >= 0)//有一个小于1 就结束了，循环写的是继续，所以是&&
    {
        if(nums1[end1]>nums2[end2])
        {
            nums1[dst--] = nums1[end1--];
        }
        else
        {
            nums1[dst--]= nums2[end2--];
        }
    }
     // num2中的元素可能没有搬移完，将剩余的元素继续往nums1中搬移
    while(end2 >= 0)
    {
        nums1[dst--] = nums2[end2--];
    }

}