Solution
link
The logic of this problem is quite simple:
- treat the given array which is divided at the position n as two parts.
- use n as the iterator(reduce the cost of For Loop to O(len(array)/2)), then add each element into the result array
I made two submissions to solve this problem, all the lines are the same except one line inside the For Loop , which made a huge difference in the time complexity.
Submissions
- faster than 39.93%:
class Solution:
def shuffle(self, nums: List[int], n: int) -> List[int]:
result=[]
for i in range(n):
result+=[nums[i],nums[i+n]]
return result
- faster than 95.78%:
class Solution:
def shuffle(self, nums: List[int], n: int) -> List[int]:
result=[]
for i in range(n):
result+=[nums[i]]+[nums[i+n]]
return result
Analysis
result+=[nums[i],nums[i+n]]
has the same effect as:
result.extend([nums[i],nums[i+n]])
# O(k),k is the number of elements inside the extending list
result+=[nums[i]]+[nums[i+n]]
has the same effect as:
result.append(nums[i]) # O(1)
result.append(nums[i+1]) # O(1)
I wrote a complement post to this topic:
https://dev.to/effylh/internal-implements-of-list-extend-and-list-append-operations-in-python-4p8j
Summary
We're familiar with those methods, but we still need to pay attention about the time complexity and make the most appropriate choice.
Method Time Complexity:
append() O(1)
insert() O(n)
extend() O(k)
Top comments (0)