各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 84 天。今天力扣上的每日一题是「26. 删除有序数组中的重复项」。

解题思路

题意：删除有序数组重复项，把去重后的数字放在输入数组的前面 n 个位置，返回 n.

看到题目标题的第一反应，当然是用 set ！set 就是为了实现去重的。但是题目要求我们进行原地操作，并且时间复杂度是 $O(1)$，因此就不能开辟另外的空间。

双指针

题目需要我们把去重后的结果保存到原本的数组中，所以想到必须有一个指针指向当前需要把结果放在哪个位置。还要一个指针指向当前应该放到哪个元素。

  • 慢指针作为基准，快指针用于寻找与慢指针不同的元素。
  • 如果快指针和慢指针指向的元素不等，则把快指针指向的元素放到慢指针的下一个位置。
  • 慢指针右移，把新的元素作为基准。

代码

给了 Python, C++, Java 三种不同的写法。

  1. class Solution(object):
  2.     def removeDuplicates(self, nums):
  3.         N = len(nums)
  4.         left = 0
  5.         for right in range(1, N):
  6.             if nums[right] != nums[left]:
  7.                 left += 1
  8.                 nums[left] = nums[right]
  9.         return left + 1
  1. class Solution {
  2. public:
  3.     int removeDuplicates(vector<int>& nums) {
  4.         const int N = nums.size();
  5.         if (N == 0) return 0;
  6.         int left = 0;
  7.         for (int right = 1; right < N; ++right) {
  8.             if (nums[left] != nums[right]) {
  9.                 nums[++left] = nums[right];
  10.             }
  11.         }
  12.         return left + 1;
  13.     }
  14. };
  1. class Solution {
  2.     public int removeDuplicates(int[] nums) {
  3.         if (nums.length == 0) return 0;
  4.         int left = 0;
  5.         for (int right = 1; right < nums.length; right++) {
  6.             if (nums[right] != nums[left]) {
  7.                 nums[++left] = nums[right];
  8.             }
  9.         }
  10.         return left + 1;
  11.     }
  12. }
  • 时间复杂度：$O(N)$
  • 空间复杂度：$O(1)$

刷题心得

今天题目不难，定义任何一个变量的时候，都要清晰记得这个变量的含义。

参考资料：

26. Remove Duplicates from Sorted Array

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家 AC 多多，Offer 多多！我们明天再见！