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

红太狼 2023-10-09 15:04 28阅读 0赞

**LeetCode官网题目地址：**[力扣][Link 1]

**Java实现代码：**

package array;
     
     /**
      * @ClassName LeetCode26
      * @Description 删除有序数组中的重复项
      * @Author Jiangnan Cui
      * @Date 2022/10/28 22:37
      * @Version 1.0
      */
     public class LeetCode26 {
         /**
          * @MethodName removeDuplicates
          * @Description 方法1：新建数组，需要开辟额外的空间
          *              时间复杂度：O(n)
          *              空间复杂度：O(n)
          *              但不满足题目要求
          * @param: nums
          * @return: int
          * @Author Jiangnan Cui
          * @Date 23:17 2022/10/28
          */
         public int removeDuplicates(int[] nums) {
             // 获得数组长度
             int length = nums.length;
             // 长度为0或1时直接返回
             if(length == 0 || length == 1){
                 return length;
             }
             // 其它情况下进行下面操作
             // 新建数组，并指定长度，初始元素全部为0
             int[] result = new int[nums.length];
             // 用下标k记录有效元素的位置
             int k = 1;
             result[0] = nums[0];
             // 从第二个元素（下标为1）开始遍历数组
             for (int i = 1; i < length; i++) {
                 // 当后一个元素和前一个元素不相等时，就把后一个元素存入有效位置
                 if(nums[i] != nums[i - 1]){
                     // 把不重复的元素存入新数组，同时有效位置右移加1
                     result[k++] = nums[i];
                 }
             }
             // 为了满足题目输出数组结果，进行元素替换(0~k-1)
             for (int i = 0; i < k; i++) {
                 nums[i] = result[i];
             }
             return k;
         }
     
         /**
          * @MethodName removeDuplicates2
          * @Description 方法2：双指针法
          *              时间复杂度：O(n)
          *              空间复杂度：O(1)
          *              满足题目要求
          * @param: nums
          * @return: int
          * @Author Jiangnan Cui
          * @Date 23:17 2022/10/28
          */
         public int removeDuplicates2(int[] nums) {
             // 获得数组长度
             int length = nums.length;
             // 长度为0或1时直接返回
             if(length == 0 || length == 1){
                 return length;
             }
             // 其它情况下进行下面操作
             // 用下标k记录有效元素的位置
             int k = 1;
             // 从第二个元素（下标为1）开始遍历数组
             for (int i = 1; i < length; i++) {
                 // 当后一个元素和前一个元素不相等时，就把后一个元素存入有效位置
                 if(nums[i] != nums[i - 1]){
                     // 把不重复的元素存入有效位置，同时有效位置右移加1
                     nums[k++] = nums[i];
                 }
             }
             return k;
         }
     
         /**
          * @MethodName removeDuplicates3
          * @Description 方法3：对方法2进行优化，相同位置时不进行元素赋值操作
          *              时间复杂度：O(n)
          *              空间复杂度：O(1)
          *              满足题目要求
          * @param: nums
          * @return: int
          * @Author Jiangnan Cui
          * @Date 23:17 2022/10/28
          */
         public int removeDuplicates3(int[] nums) {
             // 获得数组长度
             int length = nums.length;
             // 长度为0或1时直接返回
             if(length == 0 || length == 1){
                 return length;
             }
             // 其它情况下进行下面操作
             // 用下标k记录有效元素的位置
             int k = 1;
             // 从第二个元素（下标为1）开始遍历数组
             for (int i = 1; i < length; i++) {
                 // 当后一个元素和前一个元素不相等时，就把后一个元素存入有效位置
                 if(nums[i] != nums[i - 1]){
                     // 如果两个位置元素不相等，就进行赋值，同时k加1右移
                     if(nums[i] != nums[k]){
                         nums[k] = nums[i];
                     }
                     // 如果两个位置元素相等，不进行赋值，但需要k加1右移
                     k++;
                 }
             }
             return k;
         }
     
         /**
          * @MethodName removeDuplicates4
          * @Description 方法4：双指针法for循环实现
          *              时间复杂度：O(n)
          *              空间复杂度：O(1)
          *              满目题目要求
          * @param: nums
          * @return: int
          * @Author Jiangnan Cui
          * @Date 23:17 2022/10/28
          */
         public int removeDuplicates4(int[] nums) {
             // 获得数组长度
             int length = nums.length;
             // 长度为0或1时直接返回
             if(length == 0 || length == 1){
                 return length;
             }
             // 其它情况下进行下面操作
             // 用下标k记录有效元素的位置
             int k = 1;
             // 用i记录遍历元素的位置
             int i = 1;
             while(i < length){
                 // 当后一个元素和前一个元素不相等时，就把后一个元素存入有效位置
                 if(nums[i] != nums[i - 1]){
                     // 如果两个位置元素不相等，就进行赋值，同时k加1右移
                     if(nums[i] != nums[k]){
                         nums[k] = nums[i];
                     }
                     // 如果两个位置元素相等，不进行赋值，但需要k加1右移
                     k++;
                 }
                 // 判断结束后，i加1继续向右遍历
                 i++;
             }
             return k;
         }
     
         /**
          * @MethodName removeDuplicates5
          * @Description 方法5：改变方法4边界条件，测试使用
          *              时间复杂度：O(n)
          *              空间复杂度：O(1)
          *              满足题目要求
          * @param: nums
          * @return: int
          * @Author Jiangnan Cui
          * @Date 23:17 2022/10/28
          */
         public int removeDuplicates5(int[] nums) {
             // 获得数组长度
             int length = nums.length;
             // 长度为0或1时直接返回
             if(length == 0 || length == 1){
                 return length;
             }
             // 其它情况下进行下面操作
             // 用下标k记录有效元素的位置
             int k = 1;
             // 用i记录遍历元素的位置
             int i = 1;
             while(i <= length - 1){
                 // 当后一个元素和前一个元素不相等时，就把后一个元素存入有效位置
                 if(nums[i] != nums[i - 1]){
                     // 如果两个位置元素不相等，就进行赋值，同时k加1右移
                     if(nums[i] != nums[k]){
                         nums[k] = nums[i];
                     }
                     // 如果两个位置元素相等，不进行赋值，但需要k加1右移
                     k++;
                 }
                 // 判断结束后，i加1继续向右遍历
                 i++;
             }
             return k;
         }
     
         public static void main(String[] args) {
             int[] nums = {1,1,2};
             int i = new LeetCode26().removeDuplicates(nums);
             System.out.println("i = " + i);
             int[] nums2 = {1,1,2};
             int i2 = new LeetCode26().removeDuplicates2(nums2);
             System.out.println("i2 = " + i2);
             int[] nums3 = {1,1,2};
             int i3 = new LeetCode26().removeDuplicates3(nums3);
             System.out.println("i3 = " + i3);
             int[] nums4 = {1,1,2};
             int i4 = new LeetCode26().removeDuplicates4(nums4);
             System.out.println("i4= " + i4);
             int[] nums5 = {1,1,2};
             int i5 = new LeetCode26().removeDuplicates5(nums5);
             System.out.println("i5 = " + i5);
     
             int[] nums6 = {0,0,1,1,1,2,2,3,3,4};
             int i6 = new LeetCode26().removeDuplicates(nums6);
             System.out.println("i6 = " + i6);
             int[] nums7 = {0,0,1,1,1,2,2,3,3,4};
             int i7 = new LeetCode26().removeDuplicates2(nums7);
             System.out.println("i7 = " + i7);
             int[] nums8 = {0,0,1,1,1,2,2,3,3,4};
             int i8 = new LeetCode26().removeDuplicates3(nums8);
             System.out.println("i8 = " + i8);
             int[] nums9 = {0,0,1,1,1,2,2,3,3,4};
             int i9 = new LeetCode26().removeDuplicates4(nums9);
             System.out.println("i9 = " + i9);
             int[] nums10 = {0,0,1,1,1,2,2,3,3,4};
             int i10 = new LeetCode26().removeDuplicates5(nums10);
             System.out.println("i10 = " + i10);
         }
     }

**输出结果：**

i = 2
     i2 = 2
     i3 = 2
     i4= 2
     i5 = 2
     i6 = 5
     i7 = 5
     i8 = 5
     i9 = 5
     i10 = 5

[Link 1]: https://leetcode.cn/problems/remove-duplicates-from-sorted-array/