[Leetcode] 27. Remove Element

Identifying the Problem

주어진 수열들 중 val 값과 같은 경우 수열에서 제거한다.

 

제한조건

• 0 <= 문자열 길이 <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100
• 새로운 배열을 생성해서는 안된다.
• 시간 복잡도는 O(1) 이여야 한다.

Organizing thoughts

buble sort의 원리를 사용해서 val을 거르는 방식을 채택하였다.

Sourcecode

(1) 내가 작성한 코드지만, 시간복잡도 O(1)을 초과한다.

int removeElement(int* nums, int numsSize, int val){

    int count = 0;
    int temp = 0;
    
    
    if(numsSize == 0) return 0;
    if(numsSize == 1 && nums[0]  == val) return 0;
    
    for(int i =0 ; i<numsSize; i++)
        if(nums[i] == val)
            count++;
    
    if(count == 0) return numsSize;
    
    for(int i = 0; i<count;i++)
        for(int k=0; k<numsSize-i-1;k++)
            if(nums[k] == val)
            {
             temp = nums[k+1];
             nums[k+1] = nums[k];
             nums[k] = temp;


            }

    
    return numsSize - count;
    
    
    
}

 

(2) 아래는 다른 사람이 작성한 코드이다.

int removeElement(int* nums, int numsSize, int val) {
    int i, start = 0;
    for (i = 0; i < numsSize; i++) {
        if(nums[i] != val)
            nums[start++] = nums[i];
    }
    return start;
}

 

 

New things learned 

• 제한 조건이 O(1)인 경우 index의 역할을 두가지로 나누면 단순화가 가능하다.