Remove Duplicates from Sorted Array

Question * Easy *

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Hints:

Example 1

1
2
3
4
5
Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2

1
2
3
4
5
Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.

My solution

可能是今天上了一天的课，弄的头晕。读题没读仔细，害的这道题解了半天，其实之前就已经做出来了！我想多测试几个testcase，结果发现已经做出来的方法没写对，然后又重新写，结果越写越复杂。所以这件事说明了仔细的重要性 。 我遇到的坑就是——–> 题目中说的 a sorted array nums. 意思就是这个数组里面的元素是已经排好顺序的。 我测试完这两个example以后发现没问题。又测试[0,1,2,2,4,3,4] 等等testcase，结果发现我的方法得不到正解。 其实是我的testcase写错了。

首先根据维基百科的解答in-place ，我的理解就是原地算法就是只在现有的数组里面操作，不额外的引入新的数组或者开辟新的空间。 仅仅是依靠输出来覆盖输入的一种算法。

理解了in-place algorithm以后， 我就谈谈我的思路。

按照顺序把数组里面的两个最近数字两两比较，如果前后不一样就用后面的数字替换前面的数字。因此这里就是for循环然后if条件判断。 但是又是一个问题，有可能有连续2个以上的数字都是一样的。比如example 2 里面 有三个1连续。 那么答案显然第一个2要替换第二个1。 由于第一个1替换了第二个0，则第一个1的index是1。 所以第一个2的index是2. 所以需要计算不同数字替换前面的连续相同数字以后的index。 我就想到了计算连续相同数字的判断次数 x. 然后用不同数字原本的index减去x得到不同数字替换连续相同数字以后的index。这样依靠后一个不同数字替换前连续相同数字，就可以得到新的nums数组。返回的integer是新的nums数组里面前面不同数字的个数。

具体的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int removeDuplicates(int[] nums) {
       if(nums.length==0){
           return 0;
       }else{
         int temp = nums[0];
         int result = 1; 
         int count = 0; 
         for (int i=1; i < nums.length; i++){   
              if(temp==nums[i]){
                  count+=1;
              }
             
              if(temp != nums[i]){                  
                    temp=nums[i];
                    nums[i-count]=nums[i];
                    result+=1;
              }
         }
       return result;  
    }
  }
}

运行结果

Example1

Example 2

More TestCase

可见我的方法没有问题。 a sorted array nums 的testcase要注意啊！

复习一下时间复杂度。 这个解法的时间复杂度是O(n).

Leetcode Clarification

在leetcode里面的clarification解释为什么返回值是integer但是答案是数组。

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

1
2
3
4
5
6
7
8
// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Leetcode的Solution

1
2
3
4
5
6
7
8
9
10
11
public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int i = 0;
    for (int j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}
  • Time complextiy : O(n). Assume that n is the length of array. Each of i and j traverses at most n steps.
  • Space complexity : O(1).

这道题应该是没什么难度。就是自己读题不仔细在testcase那里犯了错。