Oct-16-2018

争取每周做五个LeedCode题，定期更新，难度由简到难

Title: Remove Duplicates from Sorted Array

Description:

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.

Example:

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.

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.

Difficulty:

Easy

Implement Programming Language:

C#

Note：

Confused why the returned value is an integer but your answer is an array?

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:

// 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]);
}

Answer:

这里有几点要注意：

• 空间复杂度为O(1),就是说不能额外创建数组
• 最后返回的是lenth，但是前0-lenth正好要是不能重复的数字。也就是说加入只有1,3,4三个数字，那array[0]=1,array[1]=3,array[2]=4

这个题目比较简单了，就不解释太多了，直接把不同的数字直接放到前面就行，后面乱码无所谓，虽然破坏了原数据，但是不影响需求。

public static int RemoveDuplicates(int[] nums)
        {
            if (nums.Length <= 1)
                return nums.Length;

            int lenth = 0;
            for (int i = 0; i < nums.Length-1; i++)
            {
                if(nums[i] != nums[i + 1])
                {
                    nums[lenth] = nums[i];
                    lenth++;
                    nums[lenth] = nums[i + 1];
                }
            }
            return lenth;
        }

Github