27. Remove Element

개굴·2024년 5월 10일

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val 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 elements which are not equal to val. 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 val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

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

Example 1:

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

Example 2:

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

Constraints:

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

계획

0. 첫번째 계획

얄팍한 C 사고에서 벗어나야 한다는 것을 깨달았다.
새 공간을 쓰려는 것도 좀 그만 해야 함..
코드는 안 올리겠다 애초에 중간부터는 통과도 못함

1. 두번째 계획 - 큐

시간복잡도 계산해둔 페이지

파이썬 리스트는 큐나 스택처럼 맨 뒤나 앞을 제거할 수 있다
포문을 돌며 val와 일치할 때 삭제, 일치하지 않을 때는 뒤로 보내준 뒤에 삭제

이 방법의 문제점은 len가 변화한다는 것

2. 세번째 방법 - 비슷한 큐

포문 대신 while문을 사용 - 조건절에 nums.count(val)을 넣음
전체 길이 반환

3. 네번째 방법 - leetcode solution

index를 설정
순서대로 훑으며 val가 아닐 경우에는 nums[index]에 해당 값을 넣어줌
index값이 최종 k값

코드

1. 두번째 계획 - 큐

## 큐처럼 리스트를 쓰기
for i in range(0, len(nums)):
    if nums[0] != val:
        nums.append(nums[0])
        del nums[0]
    else:
        del nums[0]

return len(nums)

2. 세번째 방법 - 비슷한 큐

while nums.count(val):
    nums.remove(val)

return len(nums)

3. 네번째 방법 - leetcode solution

# best solution O(n) / O(1)
index = 0
for i in range(len(nums)):
    if nums[i] != val:
        nums[index] = nums[i]
        index += 1
return index

Review - 20240702

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        
        read = 0
        write = 0

        for read in range(len(nums)):
            if nums[read] != val:
                nums[write] = nums[read]
                write+=1
        
        return write