[LeetCode] #26. Remove Duplicates from Sorted Array (reapeat : 0)

문제를 제대로 안읽고 풀엇더니 오래걸렸다. non-decreasing order는 오름차순이라는 뜻이고 , 중복 값을 제거한 배열의 길이를 반환하는 문제이다. 

 

Description

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
• Return k.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

 

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

 

Solution 

class Solution{  
     public int removeDuplicate(int[] nums){
         int len = nums.length;
         int left = 0;
         int right = 1;
         
         while(right < len){
             if(nums[left] < nums[right]){
                  left++;
                  nums[left] = nums[right];
             }
             
             right++;
         
         }
         
         return left + 1;
     
     
     }
}

 

1. The elements of nums array are ordered in non-decreasing order. which means if there is a non-duplicate element next to the current element. the next element is bigger. it is nums[current] < nums[current+1]

2. This algorithm wants to get the length of the new array. So I returned left+1  because left is an index which starts from 0

 

Performance 

In terms of space complexity, It is O(1) Because it uses only three constant variables. len,left,right,nums

In terms of time complexity, It is O(n) because the main operation involes in iterating the nums array. Here n represents the number of elements in the array.