经典的数组和指针结合的OJ题

一、合并两个有序数组

leetcode链接

题目描述：

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

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

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

思路：

这种将两个有序的数组再合并得到一个全新的有序数组，最直接的办法是先将一个数组的内容拷贝到另一个数组中，然后直接对这个数组进行排序，但是这种方法空间复杂度是O(N)，时间复杂度也包含了一个排序的时间，也不见得高效，所以这种思路是不完美的。

另一个思路就是利用了合并算法的思想。

先将两个指针分别指向两个数组的最小值进行比较
取较小值的内容放在新的数组
将取较小值数组的指针向后走一位，继续重复上述的步骤

这种算法的思想的时间复杂度就大大较少，是O(M+N)。

但这一题是变形，题目中将nums1中的数组变长,使之能接收两个数组的元素，也就是说将两个数组合并后的元素全部放在了nums1数组中。思路与上述的合并算法本质是一样的，区别在于我们在两个数组中从后往前找最大值，然后尾插到nums1数组中。

源码：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
    
    int end1 = m-1;
    int end2 = n-1;
    int num = m+n-1;
    while(end1>=0 && end2>=0)
    {
        if(nums1[end1]<=nums2[end2])
        {
            nums1[num] = nums2[end2];
            end2--;
            num--;
        }
        else
        {
            nums1[num] = nums1[end1];
            end1--;
            num--;
        }
    }
//考虑到当end2>0时，也就是nums2数组没有遍历完毕，我们需要拷贝到nums1数组中
    while(end2>=0)
    {
        nums1[end2]=nums2[end2];
        end2--;
    }
}

小技巧：

在解决问题时，需要考虑不同的情况，也就是不同的样例输出，针对不同的情况去完善代码。

二、移除元素

leetcode链接

题目描述：

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

思路：

利用双指针的思想

首先将两个指针str、dst一同指向数组的首元素地址
如果指向的元素是value，那么str++，dst不动；如果指向的元素不是value，先将str指向的内容赋给dst，接着str和dst都向后走一位（核心思想）
最后返回新数组元素的个数用总个数减去相同元素的次数即可。

这种在空间和时间方面都是双赢，空间复杂度是O(1),时间复杂度是O(N)

源码：

int removeElement(int* nums, int numsSize, int val)
{
    int num = 0;
    int* dst = nums;
    int* str = nums;
    while (str <= nums + numsSize - 1)
    {
        if (*str == val)
        {
            str++;
            num++;
        }
        else
        {
            *dst = *str;
            dst++;
            str++;
        }
    }
    return numsSize-num;
}