Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution:
- def countSmaller(self, nums: List[int]) -> List[int]:
- def merge(a):
- if not a or len(a)==1:return
- n=len(a)
- m=n//2
- L,R=a[:m],a[m:]
- merge(L)
- merge(R)
- i,j,k,m,n=0,0,0,len(L),len(R)
- count=0
- while i<m and j<n:
- #print(L,R,i,j,k)
- if L[i][0]>R[j][0]:
- a[k]=R[j]
- count+=1 #we add all small numbers that are less than value at L[i] because they are inversions. We add the count of L[i] at once while we are adding L[i] to merged array
- j,k=j+1,k+1
- else:
- _,idx=L[i]
- a[k]=L[i]#so here we are adding L[i]. So we should update the count so far happened and we wont make this 0 because since array is sorted we will be using the same count for upcoming values
- ans[idx]+=count
- i,k=i+1,k+1
- while i<m:
- _,idx=L[i]
- a[k]=L[i]
- ans[idx]+=count#So far only left section elements are left. So we just fill previous count for this. Because if the count denotes no of smaller points to right side of that previous value then obviou same count will be used for current value since it is sorted
- i,k=i+1,k+1
- while j<n:
- a[k]=R[j]
- count+=1# You can just avoid.Because these are remained empty right section numbers
- j,k=j+1,k+1
- #print(L,R,ans,a)
- '''
- Why are we adding tuple (j,i) . Because when we slice we loos indexes while doing merge sort.
- '''
- a=[(j,i) for i,j in enumerate(nums)]
- ans=[0]*len(nums)
- merge(a)
- return ans
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement