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

一、合并两个有序数组

leetcode链接

题目描述：

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

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

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

思路：

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

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

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

这种算法的思想的时间复杂度就大大较少，是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) 额外空间并 原地 修改输入数组。

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

思路：

利用双指针的思想

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

这种在空间和时间方面都是双赢，空间复杂度是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;
}

小总结：

想要在数组中删除元素并不一定真的删除，可以利用指针去改变数组某些位置的元素，然后打印方式也可以根据指针改变。

三、删除有序数组中的重复项

leetcode链接

题目描述：

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

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

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

思路：

同样利用双指针，注意用双指针时，最好直接用整型代表下标，真正用双指针表示双地址还是要麻烦不少

1. 首先将两个指针指向数组的首元素地址
2. 若相同，则str++
3. 不同，先让dst++,然后让dst下标的数组指向的值等于str的值，最后让str++

源码：

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

小总结：

在已知用双指针解决题目后，自己多试几次就会找到及人体方法，重要的是如何知道这题用双指针求解！