- 一、26. 删除有序数组中的重复项
- 1.题目
- 2.我的代码
- 3.改进
- 二、83. 删除排序链表中的重复元素
- 1.题目
- 2.代码
一、26. 删除有序数组中的重复项 1.题目
- 删除有序数组中的重复项
给你一个 升序排列 的数组 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;
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;
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++ 这类语言没有自动垃圾回收的机制，确实需要我们编写代码时手动释放掉这些节点的内存。
不过话说回来，就算法思维的培养来说，我们只需要知道这种快慢指针技巧即可。
