2022.4.26 双指针I——快慢指针

文章目录

• 一、26. 删除有序数组中的重复项
• • 1.题目
  • 2.我的代码
  • 3.改进
• 二、83. 删除排序链表中的重复元素
• • 1.题目
  • 2.代码

---

一、26. 删除有序数组中的重复项 1.题目

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

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

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

2.我的代码

使用快慢指针思想（但区别于之前做链表题时快指针与慢指针移动的频率相同，步频不同的情况），这里的快、慢指针初始都从数组的第一个元素出发，fast 不停地向后移动一个单位（slow 不动），在遇到第一个与 slow 指向的值不同时，令 slow 下一个位置的值变为此时 fast 指向的值（这里包括两种情况， fast 就是 slow 的下一个位置；或 fast 已相对 slow 走过了多个单位；但无论如何，我们的动作都达到了 “将与 slow 指向的值原地删除” 的效果）。

引用GIF：

package Array;

import java.util.Arrays;

/**
 * @author: LYZ
 * @date: 2022/4/26 15:47
 * @description: 26. 删除有序数组中的重复项
 */
public class RemoveDuplicates {
    public static void main(String[] args) {
        int[] nums = {0,0,1,1,1,2,2,3,3,4};
        RemoveDuplicates removeDuplicates = new RemoveDuplicates();
        int ans = removeDuplicates.removeDuplicates(nums);
        System.out.println(ans);
        System.out.println(Arrays.toString(nums));
    }

    public int removeDuplicates(int[] nums) {
        int slow = 0;
        int fast = 0;
        int lenth = nums.length;
        int count = 1;

        while (fast < lenth) {
            if (nums[slow] == nums[fast]) {
                fast += 1;
            } else {
                nums[slow + 1] = nums[fast];
                count++;
                fast += 1;
                slow += 1;
            }
        }

        return count;
    }
}

3.改进

参考文章

我的思路和作者的基本一致，不过不必额外声明计数器，直接返回 slow + 1 即为数组删除重复元素后的新长度。

int removeDuplicates(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    int slow = 0, fast = 0;
    while (fast < nums.length) {
        if (nums[fast] != nums[slow]) {
            slow++;
            // 维护 nums[0..slow] 无重复
            nums[slow] = nums[fast];
        }
        fast++;
    }
    // 数组长度为索引 + 1
    return slow + 1;
}

二、83. 删除排序链表中的重复元素 1.题目

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

2.代码

这道题和 “26. 删除有序数组中的重复项” 思路完全相同，同样为快慢指针。只不过在链表中，需要一些更细节的 *** 作：
①最开始做时想错了，没写 slow = slow.next; 这句，并且打算最终返回 slow，这就导致无论原链表有多少不同的值，最终链表中只保留了头结点和原链表中与头结点不同的最后一个值。
②加入 slow = slow.next; 后，最终放回 head，但又落下了 slow.next = null; 导致链表没有断开与后面重复元素的连接。
③slow.next = null;在LeetCode提交时是会报空指针异常的，所以要将其放在 if 语句中。（若 slow 为空，空指针是无法拥有 next 节点的）

package LinkedList;

/**
 * @author: LYZ
 * @date: 2022/4/26 16:22
 * @description: 83. 删除排序链表中的重复元素
 */
public class DeleteDuplicates {
    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(3)))));
        DeleteDuplicates deleteDuplicates = new DeleteDuplicates();
        ListNode newHead = deleteDuplicates.deleteDuplicates(head);
        while (newHead != null) {
            System.out.println(newHead.val);
            newHead = newHead.next;
        }
    }

    public ListNode deleteDuplicates(ListNode head) {
        ListNode slow = head, fast = head;

        while (fast != null) {
            if (slow.val == fast.val) {
                fast = fast.next;
            } else {
                slow.next = fast;
                fast = fast.next;
                slow = slow.next;
            }
        }

        if (slow != null) {
            slow.next = null;
        }

        return head;
    }
}

链表中那些重复的元素并没有被删掉，就让这些节点在链表上挂着，合适吗？

这就要探讨不同语言的特性了，像 Java/Python 这类带有垃圾回收的语言，可以帮我们自动找到并回收这些「悬空」的链表节点的内存，而像 C++ 这类语言没有自动垃圾回收的机制，确实需要我们编写代码时手动释放掉这些节点的内存。

不过话说回来，就算法思维的培养来说，我们只需要知道这种快慢指针技巧即可。