删除有序数组中的重复项JAVA版

问题描述

给你一个有序数组nums,请你原地删除重复出现的元素，使得每一个元素只出现一次，返回删除后数组的新长度。

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

示例1

输入：nums = [1,1,2]

输出：2, nums = [1,2]

解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2

输入：nums = [0,0,1,1,1,2,2,3,3,4]

输出：5, nums = [0,1,2,3,4]

解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示

1：0 <=nums.length <=3*10^4

2: -10^4 <= nums[i] <=10^4

3: nums 已按升序排列

题解

这道题目要求不能使用额外的数组空间，并且在原来的数组上进行删除，额外空间是O（1）利用双指针的方法，用j去找有没有i相同的元素，如果有的话，就需要将j右移，如果没有的话，就需要将j所指元素赋给i+1 所指的元素，只有这样，我们也才将之前重复的元素给覆盖掉，最后再返回i+1,表示非重复元素的个数。

class Solution {
      public int removeDuplicates(int[] nums) {
      int i = 0 ;
      int j = i + 1 ;
      if(nums == null && nums. length == 0) 
      {
          return 0 ;
          }
       while(j < nums.length)
       {
           if(nums[j] == nums[i]){
           j++ ;
           }
           else {
              nums[i+1] = nums[j] ;
              i++ ;
              j++ ;
           }
        }
     return i+1 ;
  }
}               
           

时间复杂度是O(n),n是指数组的长度

空间复杂度是O(1),不需要额外的空间。