文章题目来源力扣
🎈力扣（LeetCode）全球极客挚爱的技术成长平台
LeetCode官网：https://leetcode-cn.com/problem-list/e8X3pBZi/

---

✨目录

1. 移除元素
2. 删除排序数组中的重复项
3. 合并两个有序数组

---

1.移除元素

---

来源：力扣（LeetCode）
题目链接：https://leetcode.cn/problems/remove-element/

• 思路一：
  遇到val值，直接把val删除，运用顺序表的删除，把后面的值往前覆盖掉val
  优点：学了顺序表后容易想到
  缺点：时间复杂度O(N^2)——>效率太低(在LeetCode上可能过不了)

思路一不作代码实现！！！

• 思路二：
  可以另开一个数组，将不是val的值拷贝到新数组里，然后再覆盖拷贝回去
  （典型的以空间换时间）
  优点：时间复杂度O(N)
  缺点：空间复杂度为O(N)不符合要求

代码实现：

int removeElement(int* nums, int numsSize, int val){
    if(nums==NULL || numsSize==0)//特殊值处理
        return 0;
    int a[numsSize];
    int i=0;
    int j=0;
    // 把不是val的值拷贝出来
    while(i<numsSize)
    {
        if(nums[i]!=val)
        {
            a[j++]=nums[i++];
        }
        else
            i++;
    }
    //覆盖拷贝回去
    i=0;
    while(i<j)
    {
        nums[i]=a[i];
        i++;
    }
    return j;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

• 思路三：（优解）
  我们可以在思路二的想法上再优化一点，思路二时间复杂度已经是最优了，但是要开辟一个数组来拷贝。
  那我们能不能不开辟新数组，直接在原数组中拷贝呢？
  答案是可以的！ 我们把原数组既当拷贝数组，又当目标数组
  优点：时间复杂度O(N),空间复杂度O(1)
• 实现方法：
  定义两个下标，一个des，一个src，遇到val值，把src往后找移，des在val值中不动，直到src找到一个不是val值的数，然后把src指向的数覆盖拷贝到des中，然后des往后移一步，src进行找不是val值重复上面工作。

• 代码代码实现

int removeElement(int* nums, int numsSize, int val){

    int des=0,src=0;
    while(src<numsSize)
    {
        if(nums[src]!=val)//把非val的值覆盖val值
        {
            nums[des++]=nums[src++];
        }
        else
        {
            src++;
        }
    }
    return des;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.删除排序数组中的重复项

---

来源：力扣（LeetCode）
题目链接：https://leetcode.cn/problems/merge-sorted-array

• 思路：
  这题跟上面移除元素有异曲同工之妙，你可以尝试用上面的思路一和思路二来解决这个题，
  我在这里只演示思路三

实现方法： 因为它们是有序的，所以我们可以像上面的思路三一样，在原地覆盖拷贝，把其中一个重复的值删掉！

• 代码实现

int removeDuplicates(int* nums, int numsSize){
    int src=0,des=0;
    while(src< numsSize)
    {
        if(nums[src]!=nums[des])
        {
            nums[++des]=nums[src++];
        }
        else
        {
         	src++;
        }
    }
    return des+1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.合并两个有序数组

---

来源：力扣（LeetCode）
题目链接：https://leetcode.cn/problems/merge-sorted-array

• 思路一：
  把nums2数组中的元素拷贝到nums1后面，然后排序
  优点：容易想到
  缺点：排序耗费时间大，我们所熟悉的排序中，最快的不过是快速排序，但它是时间复杂度是
  O(N*logN)

代码实现：自行实现！

• 思路二：
  我们可以想想，因为它本身就是有序的，我们是不是可以这样
  开一个新数组，分别比较两数组的值，把小的取下来尾插到新数组中，最后再拷贝回nums1
  优点：时间复杂度O(N+M)
  缺点：空间复杂度O(N+M)

代码实现：自行实现！

• 思路三：（优解）
  吸取思路二中的思路，我们可不可以在原地把它搞定呢？
  答案是可以的！
  因为nums1中的后面的位置足已把nums2放进去，我们可以把nums1的后面位置当作新数组，
  但是我们不能取小了，要转换思路，取大的放在nums1后面！！！

但是这样的方法会分两种情况：

• 情况一：nums2先结束
  

• 情况二：nums1先结束
  

• 代码实现：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int end1=m-1, end2=n-1,i=m+n-1;

    while( end1>=0 && end2>=0 )
    {
        if(nums1[end1] > nums2[end2] )
        {
            nums1[i--]=nums1[end1--];
        }
        else
        {
            nums1[i--]=nums2[end2--];
        }
    }

    //num2没结束
    while(end2>=0)
    {
        nums1[i--]=nums2[end2--];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---