题目地址(26. 删除有序数组中的重复项)

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

题目描述

  1. 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
  3. 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
  7. 说明:
  9. 为什么返回数值是整数，但输出的答案是数组呢?
  11. 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
  13. 你可以想象内部操作如下:
  15. // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
  16. int len = removeDuplicates(nums);
  18. // 在函数里修改输入数组对于调用者是可见的。
  19. // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
  20. for (int i = 0; i < len; i++) {
  21.     print(nums[i]);
  22. }
  26. 示例 1：
  28. 输入：nums = [1,1,2]
  29. 输出：2, nums = [1,2]
  30. 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
  33. 示例 2：
  35. 输入：nums = [0,0,1,1,1,2,2,3,3,4]
  36. 输出：5, nums = [0,1,2,3,4]
  37. 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
  42. 提示：
  44. 0 <= nums.length <= 3 * 104
  45. -104 <= nums[i] <= 104
  46. nums 已按升序排列

前置知识


公司

  • 暂无

思路

关键点

  • image.png

  • image.png

    代码

  • 语言支持：Java

Java Code:

  1. class Solution {
  2.         public int removeDuplicates(int[] nums) {
  3.             //如果数组长度为0 就返回0
  4.             if (nums.length == 0) {
  5.                 return 0;
  6.             }
  7.             int slow = 1;
  8.             //fast遍历的次数为数组的长度 如果数组的fast当前的数值!=fast-1的话 因为数组是有序排列的 所以后面就不会有与fast相等的数字了
  9.             //这时使slow下标的数字=fast下下标的数字 再使slow++ 这样slow就是所有不相等的数字的集合. 返回slow的值也就是新数组的长度了
  10.             for (int fast=1 ; fast < nums.length; fast++) {
  11.                 if (nums[fast] != nums[fast - 1]) {
  12.                     nums[slow++] = nums[fast];
  13.                 }
  14.             }
  15.             return slow;
  16.         }
  17.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：26. 删除有序数组中的重复项(2) - 图3#card=math&code=O%28n%29&id=pXMHR)
  • 空间复杂度：26. 删除有序数组中的重复项(2) - 图4#card=math&code=O%28n%29&id=sUcWK)