数据结构·顺序表经典例题(双指针)

? ? ? ? 本节讲解两道顺序表经典例题，运用到了双指针的思想

? ? ? ? 双指针并不是两个指针，而是用两个类似指针的东西去扫描数组，以达到简化运算的效果

1. 移除元素

? ? ? ? OJ链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

? ? ? ? 本体给出一个数组 nums 和一个值 val 。目标是在不创建新数组的情况下，在这个数组本体上的内容中删掉所有值是?val 的元素。

1.1 解题思路

1.1.1 方法一

? ? ? ? 遍历数组，每找到一次val就把后面的所有数据往前挪一位，覆盖掉这个val。很明显，这种两层for循环的写法效率是低下的

????????????????????????????????

1.1.2 方法二：双指针

? ? ? ? 创建两个变量 src(source) 和 dst(destination) 他俩就作为双指针管理这个数组。dst控制下一次写入的地方，src控制下一次写入的内容。

? ? ? ? 解题思路就是让src往后扫描，扫到 val 就跳过，扫到 !val 就写到dst指向的位置，等src扫完整个数组之后det就标记了所有 !val 的有效数据的结尾

? ? ? ? 扫描开始和扫描结束时候的样子就如上图一样，读者可以想像一下扫描中间的过程

? ? ? ? 最后附上本题代码：

int removeElement(int* nums, int numsSize, int val)
{
    int src = 0, dst = 0;
    //用src扫描整个数组
    while (src < numsSize)
    {
        //如果src碰到非val
        if (nums[src] != val)
        {
            //将数据拿到前面
            nums[dst] = nums[src];
            dst++;
            src++;
        }
        //如果src碰到val就什么都不做
        else
        {
            src++;
        }
    }
    return dst;
}

????????

2.??合并两个有序数组

? ? ? ? OJ链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

? ? ? ? 本体给出两个按非递减顺序排好的数组 nums1 和 nums2 它们中的有效数据分别有 m 和 n 个，nums1的长度是m+n 就是说数组 nums1 中有足够空间存下两个数组的所有有效元素。本体目的是将nums2中的数据放到nums1中，并保证 nums1 中的所有数据是按非递减顺序排序的

???????????????????????

2.1 解题思路

2.1.1 方法一

? ? ? ? 把 nums2 中的数据无脑用 strcat() 放到 nums1 的后面，然后用 qsort 给 nums1 排序

2.1.2 方法二：双指针思路

? ? ? ? 这道题我们要先思考好指针要怎么放，如果从前面开始扫描并插入数据的话，势必会造成后面数据的整体挪移，这是双指针算法不想看到的。

? ? ? ? 所以我们让指针从后向前扫描，我们设置3个指针，l1 和 l2 比较，谁大就放到 l3 的位置去，这样的话就不会妨碍到有效数据，也就是说不用整串挪移数据了，简单来讲就是说总是把两个数组中最大的那个值放到最后那个空着的位置

????????????????????????????????????????????????????????????????????

? ? ? ? 但是有一些特殊的情况要注意一下，就是当 l1 扫完了但是 l2 没扫完，这种情况下再把nums2中的内容直接都粘到 l3 那里就行了

? ? ? ? ??

? ? ? ? 最后是本题代码：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
	int l1 = m - 1, l2 = n - 1, l3 = m + n - 1;

	//l1 l2从后往前扫描，把最大的数放到后面
	while (l1 >= 0 && l2 >= 0)
	{
		if (nums1[l1] > nums2[l2])
		{
			nums1[l3] = nums1[l1];
			l1--;
			l3--;
		}
		else
		{
			nums1[l3] =nums2[l2];
			l2--;
			l3--;
		}
	}

	//此时处理特殊情况
	while (l2 >= 0)
	{
		nums1[l3] = nums2[l2];
		l2--;
		l3--;
	}
}