27. Remove Element

풀이

첫 번째 풀이 O(n^3)

관련 시간복잡도

• list 에서의 item in list : O(n)
• list 의 remove(item) : O(n)

class Solution(object):
    def removeElement(self, nums, val):

        k= len(nums)
        while val in nums: #O(n^2)
            nums.remove(val) #O(n)
        
        print(k)

        return k
        

두 번째 풀이 O(nlogN)

관련 시간복잡도

• sort() : O(nlogN)
• list 의 pop() : O(1)

class Solution(object):
    def removeElement(self, nums, val):
        k = 0
        for i in range(len(nums)): #O(n)
            if val == nums[i]:
                nums[i] = 200
                k += 1
        
        nums.sort() #O(nlogN)

        for i in range(k): #O(n)
            nums.pop() #O(1)
        
        return len(nums)

세 번째 풀이 O(n)

class Solution(object):
    def removeElement(self, nums, val):
        deleted = 0
        for i in range(len(nums)): #O(n)
            if nums[i] != val:
                nums[i], nums[deleted] = nums[deleted], nums[i]
                deleted += 1
        
        nums[:] = nums[:deleted]
        
        return len(nums)