想要精通算法和SQL的成长之路 - 双指针【数组】

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 合并两个有序数组

原题链接

抓住重点信息：

• 两个数组都是非递减顺序排列。
• num1数组，末尾包含了长度为n的0序列。

思路：

1. 我们用两个指针n1,n2，分别指向两个数组的末尾（不包含元素0）。从后往前遍历。同时用一个指针right，代表当前遍历到的数组num1的索引（包含元素0）
2. 遍历的条件就是：n1 >= 0 && n2 >= 0。
3. 遍历终止的情况：如果是num2数组遍历完毕，说明数组合并完成，那么直接返回即可。如果是num1数组遍历完毕，说明num2还有部分元素没有合并到num1中，那么把剩余的num2元素插入到num1的最前端即可。

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int n1 = m - 1, n2 = n - 1, right = m + n - 1;
    while (n1 >= 0 && n2 >= 0) {
        // 从后往前遍历，大的数字先放到末尾
        nums1[right--] = nums1[n1] > nums2[n2] ? nums1[n1--] : nums2[n2--];
    }
    // 把num2中剩余的部分补充到num1的前面即可
    System.arraycopy(nums2, 0, nums1, 0, n2 + 1);
}
1
2
3
4
5
6
7
8
9

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

原题链接

思路：

1. 我们准备两个指针：left和right，并维护一个count变量。
2. 当两个指针对应的数字相等的时候，count数加1，如果<=2的时候，给nums[left]赋值，并且左指针向后移动一位。
3. 当两个指针对应的数字不等的时候，count数重置为1，nums[left]赋值。左右指针同时往后移动一位。

代码如下：

public int removeDuplicates(int[] nums) {
    int left = 0, count = 1;
    for (int right = 1; right < nums.length; right++) {
        if (nums[right] == nums[left]) {
            count++;
            if (count <= 2) {
                nums[++left] = nums[right];
            }
        } else {
            count = 1;
            nums[++left] = nums[right];
        }
    }
    // 返回的是新数组的长度，因此要在索引的基础上+1.
    return left + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16