[LeetCode] - Remove Element

Given an array nums and a value val, remove all instances of that value in-place 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.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Clarification:

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 a modification to the input array will be known to the caller as well.

 

내가 생각한 문제의 요구사항은 이렇다.

주어진 배열에서  val값을 제외한 element의 총 갯수와 val을 제외한 element들이 배열 앞에 위치하도록 조정하시오

 

1차시도

class Solution {
    public int removeElement(int[] nums, int val) {
        /*추가 메모리 공간을 사용하지 않고 가지고 있는 배열로
        nums에 있는 val 값을 제거하라
        음 자바에서 배열은 이미 고정된 크기를 가지고 있기에 삭제하려면
        ArrayList등의 추가적인 메모리를 사용하여 해당 원소를 제외하고 추가하는 방법
        말고 자바에서 직접적으로 해당 요소를 제거하는 방법은 없던것으로 기억한다.
        그렇다면?
        문제의 요구는 val을 제외한 나머지 배열 요소의 총 갯수와 나머지 배열 요소를 담은
        배열을 return해야 한다.
        ex1에서보면 [2,2,3,3] 또는 [2,2,0,0]으로 반환해도 accepted된다고 한다.
        ex2에서도 val을 제외한 총 개수는 필요하나 
        nums배열에 val인 2가 포함되어도 상관없다는 말로 보인다.
        그럼 val의 위치를 나머지 보다 뒤로 미루면 될 것 같다.
        
        1. val 제외한 element의 count구하기
        2. val을 nums 뒤쪽에 위치하게 하기 -> temp
        */
        int count = 0;
        int len = nums.length-1;
        for(int idx : nums) {
            if(nums[idx] != val) count++;
        }
        
        if(count == 0) return 0;
        if(count == leng) return leng;
        
        int answer = count;
        int idx = 0;
        while(count > 0){
            int temp = nums[idx];
            if(temp == val && nums[len] != val){
                nums[idx] = nums[len];
                nums[len] = temp;
                count--;
            }
        }
        
        
        return answer;
    }
}

시간 초과

2차시도

class Solution {
    public int removeElement(int[] nums, int val) {
        /*추가 메모리 공간을 사용하지 않고 가지고 있는 배열로
        nums에 있는 val 값을 제거하라
        음 자바에서 배열은 이미 고정된 크기를 가지고 있기에 삭제하려면
        ArrayList등의 추가적인 메모리를 사용하여 해당 원소를 제외하고 추가하는 방법
        말고 자바에서 직접적으로 해당 요소를 제거하는 방법은 없던것으로 기억한다.
        그렇다면?
        문제의 요구는 val을 제외한 나머지 배열 요소의 총 갯수와 나머지 배열 요소를 담은
        배열을 return해야 한다.
        ex1에서보면 [2,2,3,3] 또는 [2,2,0,0]으로 반환해도 accepted된다고 한다.
        ex2에서도 val을 제외한 총 개수는 필요하나 
        nums배열에 val인 2가 포함되어도 상관없다는 말로 보인다.
        그럼 val의 위치를 나머지 보다 뒤로 미루면 될 것 같다.
        
        1. val 제외한 element의 count구하기
        2. val을 nums 뒤쪽에 위치하게 하기 -> temp
        */
        int count = 0;
        int len = nums.length-1;
        for(int idx : nums) {
            if(nums[idx] != val) count++;
        }
        
        if(count == 0) return 0;
        if(count == len) return len;
        
        int answer = count;
        int idx = 0;
        while(idx <= len){
            int temp = nums[idx];
            if(temp == val){
                if(nums[len] != val){
                    nums[idx] = nums[len];
                    nums[len] = temp;
                    count--;
                }else{
                    len--;
                }
            }else{
                idx++;
            }
        }
        return answer;
    }
}
Error
Input [0,1,2,2,3,0,4,2] 2
Output [0,1,4,0]
Expected [0,1,4,0,3]

 

---

시간 많이 걸려서 정답봤습니다.

class Solution {
      public int removeElement(int[] nums, int val) {
      int i = 0;
      for (int j = 0; j < nums.length; j++) {
          if (nums[j] != val) {
              nums[i] = nums[j];
              i++;
          }
      }
      return i;
  }
}

Complexity analysis

Time complexity : 
O(n)O(n). Assume the array has a total of nn elements, 
both ii and jj traverse at most 2n2n steps.

Space complexity : O(1)O(1).

 

public int removeElement(int[] nums, int val) {
    int i = 0;
    int n = nums.length;
    while (i < n) {
        if (nums[i] == val) {
            nums[i] = nums[n - 1];
            // reduce array size by one
            n--;
        } else {
            i++;
        }
    }
    return n;
}

Complexity analysis

Time complexity : O(n)O(n). Both ii and nn traverse at most nn steps.
In this approach, the number of assignment operations is equal to the number of elements to remove.
So it is more efficient if elements to remove are rare.

Space complexity : O(1)O(1).