每日精讲：删除有序数组中的重复项，移除元素，合并两个有序数组

一       移除元素

     1题目链接：27. 移除元素 - 力扣（LeetCode）

      2题目描述：

         给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

        假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

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

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

3思路：这里有很多种比如我们先合并两个数组在进行排序，但是由于这种方法的时间空间复杂度太大所以我们一般不采用这种发放。这里我们使用简便方法双指针法（不是创建两个指针而是创建俩个变量分别指向数组的俩个位置）

以示例 1：为例

这里我们定义两个变量让他们指向数组的头部，让src做探头判断是否与val值相等

dst用于站岗。

这里有两种情况即nums[src]等于val的值和nums[src]不等于val的值

1当nums[src]==val时，src++

2当nums[src]！=val时，先赋值nums[dst]=nums[src]，再dst++,src++

我们这里用src1当探头所以当src==numsSize时跳出循环，因为只有nums[src]！=val时，dst++所以此时dst的值就是不等于 val 的元素的个数所以我们返回dst的值便可

代码实现

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

可以看到分支语句中有重复代码，可以进一步优化：

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];
       dst++;
    }
   
    src++;
   }
   return dst;
}

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

   1   题目链接：26.删除有序数组中的重复项

   2   题目描述：

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

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

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

示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]

解释：函数应该返回新的长度

2

并且原数组 nums 的前两个元素被修改为

1,2

不需要考虑数组中超出新长度后面的元素。

3思路：因为数组是一个非严格递增排列的数组所以重复项一定相邻，这里也有很多方法这里我们使用双指针法。

以示例 1：为例

     这里创建两个变量让它们分别指向数组起始位置和下一个位置，依次判断指向数组元素的值是否相等，所以我们这里有两种情况。

在src往后遍历中：

        1.nums[dst] == nums[src]，src++

        2.nums[dst] != nums[src]，dst++，nums[dst] = nums[src]，src++ 

       当src == numsSize时，跳出循环，此时dst+1等于有效数据k，最后返回dst即可。

       这里我们有一个重要问题就是当第二种情况中dst==src时赋值和不赋值都一样这就存在重复赋值所以我们要进入第二步我们可以加入两个条件即（ .nums[dst] != nums[src]  && src != dst)。

代码实现

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

可以看到分支语句中有重复代码，可以进一步优化：

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

三      合并两个有序数组

1题目链接：88. 合并两个有序数组 - 力扣（LeetCode）

2题目描述：

        给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。

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

示例 1：输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

3思路：

      3.1思路一：先合并数组，在对数组进行排序

             以实例1为例，合并后数组：（合并后再对数组进行冒泡排序或快速排序，这里以冒泡排序实现）

代码实现

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    if (nums2 == NULL)
    {
        return;
    }
   //合并数组
   int l1 = m;
   int l2 = 0;
   int l3 = m + n;
   while(l1 < l3)
   {
    nums1[l1++] = nums2[l2++];
   }
   //排序
   for (int i = 0;i<l3-1;i++)
   {
    for (int j = 0;j<l3 - 1 - i;j++)
    {
        if (nums1[j]>nums1[j+1])
        {
            int tmp = nums1[j];
            nums1[j] = nums1[j+1];
            nums1[j+1] = tmp;
        }
    }
   }

}

时间复杂度O(n^2) ，空间复杂度O(1)

3.2思路二：从后往前遍历数组

因为两个数组都是非递减顺序 排列的整数数组所以我们只要不断比较两个数组中最大的元素

再让大的值存人数组的最后依次遍历。

当其中一个数组遍历完就结束循环，这时就有两种情况分别是

数组1越界，将nums2中剩余元素按从后往前的顺序导入l1中。 

数组2越界，说明nums2中元素已经排序完成。

这里我们定义l1指向nums1数组中的尾元素，l2指向nums2数组中的尾元素，l3指向nums1数组的尾部。 

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--] = nums[l1--];
     }
     else{
        nums1[l3--] = nums2[l2--];
     }
}

控制循环条件为l1与l2不越界，在循环中从后往前比大小，大的元素放在数组尾部。

        跳出循环时：（两种情况）

若l1>=0为假，l1越界，将nums2中剩余元素按从后往前的顺序导入l1中。 

若l2>=0为假，l2越界，说明nums2中元素已经排序完成。

while(l2>=0)
{
   nums1[l3--] = nums2[l2--];
}

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--];
        }
    }    
    //若l1>=0为假，l1越界，将nums2中剩余元素按从后往前的顺序导入l1中
    while(l2>=0)
    {
        nums1[l3--] = nums2[l2--];
    }
    //若l2>=0为假，l2越界，说明nums2中元素已经排序完成
}