Leetcode算法Java全解答--80. 删除排序数组中的重复项 II

一时失言乱红尘 2022-04-03 10:24 160阅读 0赞

# Leetcode算法Java全解答–80. 删除排序数组中的重复项 II #

### 文章目录 ###

*  Leetcode算法Java全解答--80. 删除排序数组中的重复项 II
 *   *  题目
     *  想法
     *  结果
     *  总结
     *  代码
     *   *  我的答案
         *  大佬们的答案
         *  测试用例
     *  其他

## 题目 ##

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。  
说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
    int len = removeDuplicates(nums);
    
    // 在函数里修改输入数组对于调用者是可见的。
    // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
    for (int i = 0; i < len; i++) {
        print(nums[i]);
    }

示例:

示例 1:
    
    给定 nums = [1,1,1,2,2,3],
    
    函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。
    
    你不需要考虑数组中超出新长度后面的元素。
    示例 2:
    
    给定 nums = [0,0,1,1,1,1,2,3,3],
    
    函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。
    
    你不需要考虑数组中超出新长度后面的元素。

## 想法 ##

1.  先编历第一列的数据，找到那个比target大的数据，那么target在这一项的前一行(遍历1/10/23)

在关键行使用二分查找

2.陈独秀方法(better)，把二维数组转换成一个一维数组，直接上二分查找

坐标转换：matrix\[i\]\[j\] <=> matrix\[a\] 其中a=i\*n+j， i=a/n, j=a%n;

## 结果 ##

超过98%的测试案例

时间复杂度/空间复杂度：n/1

## 总结 ##

## 代码 ##

### 我的答案 ###

public int removeDuplicates(int[] nums) {
            if (nums.length < 3) {
                return nums.length;
            }
    
            int index1 = 1;
            int index2 = 1;
            int preNum = nums[0];
            int count = 1;
    
            while (index2 < nums.length) {
                nums[index1] = nums[index2];
                if (nums[index2] != preNum) {
                    preNum = nums[index2];
                    count = 1;
                    index1++;
                } else {
                    count++;
                    if (count <= 2) {
                        index1++;
                    }
                }
                index2++;
    
            }
    
            return index1;
        }

### 大佬们的答案 ###

### 测试用例 ###

@Test
        public void test080() {
            // 创建测试案例
            int[] arr1 = new int[] { 1, 1, 1, 2, 2, 3 };
            int[] arr2 = new int[] { 0, 0, 1, 1, 1, 1, 2, 3, 3 };
    
            // 测试案例期望值
            int expResult1 = 5;
            int expResult2 = 7;
    
            // 执行方法
            Solution080 solution080 = new Solution080();
            int result1 = solution080.removeDuplicates(arr1);
            int result2 = solution080.removeDuplicates(arr2);
    
            // 判断期望值与实际值
            Assert.assertEquals(expResult1, result1);
            Assert.assertEquals(expResult2, result2);
        }

## 其他 ##

代码托管码云地址：[https://gitee.com/lizhaoandroid/LeetCodeAll.git][https_gitee.com_lizhaoandroid_LeetCodeAll.git]

查看其他内容可以点击专栏或者我的博客哈：[https://blog.csdn.net/cmqwan][https_blog.csdn.net_cmqwan]

“大佬们的答案” 标签来自leetcode，侵权请联系我进行删改

如有疑问请联系，联系方式：QQ3060507060

[https_gitee.com_lizhaoandroid_LeetCodeAll.git]: https://gitee.com/lizhaoandroid/LeetCodeAll.git
[https_blog.csdn.net_cmqwan]: https://blog.csdn.net/cmqwan