class Solution(object): def removeElement(self, nums, val): """ :type nums: List[int] :type val: int :rtype: int """ while val in nums: nums.remove(val) return len(nums)
Thank you for your reply.
I'm a beginner learning programming so I'm a little confused. Could you please tell me why it's very bad? I checked "Accepted Solutions Runtime Distribution" and it says that the runtime beats 88.80 % of python submissions. So what's good and what's bad for an algorithm?
Well it's only O(n2). And O(n) is easy. It just seems fast because the judge is very weak here, only has tiny test cases. Maybe because this is from the earliest days of LeetCode.
Got it. Thank you for you explaination. The return statement is left out because of my misunderstanding. These codes can be accepted without return statement, and the description says " you must do this in place ", so I think it's enough to change the nums without return anything. My fault.
@bluesweater If it's accepted without return statement, that's a bug in the judge. It shouldn't get accepted. Probably the judge does something like checking
nums[:output], which without return statement turns into
nums[:None], which is a copy of the whole
nums. Combined with your actual shrinking of the list, that then appears to be correct.
Anyway, here's a little test, testing your solution and the normal O(n) solution on a certain input with 10,000 elements (which isn't very big, I think some more recent problems have inputs with 100,000 elements or so):
from time import time class Solution(object): def removeElement(self, nums, val): nums =  * 5000 +  * 5000 val = 1 t0 = time() while val in nums: nums.remove(val) print time() - t0 nums =  * 5000 +  * 5000 t0 = time() i = 0 for num in nums: if num != val: nums[i] = num i += 1 print time() - t0
Doing "Run Code" with that prints times like these:
So already for this medium size input, your code is over 1000 times slower than the normal solution.
I've learned a lot. Thank you so much~
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.