Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- https://practice.geeksforgeeks.org/problems/inversion-of-array-1587115620/1
- Method 2:
- #concise
- class Solution:
- def inversionCount(self, arr, n):
- # Your Code Here
- count=0
- def merge(a):
- nonlocal count
- if len(a)==1 or 0:return a
- mid=len(a)//2
- L,R=a[:mid],a[mid:]
- merge(L)
- merge(R)
- m,n=len(L),len(R)
- i,j,k=0,0,0
- while i<m and j<n:
- if L[i]<=R[j]:
- a[k]=L[i]
- i,k=i+1,k+1
- else:
- a[k]=R[j]
- count+=(m-i)
- j,k=j+1,k+1
- while i<m:
- a[k]=L[i]
- i,k=i+1,k+1
- while j<n:
- a[k]=R[j]
- j,k=j+1,k+1
- return a
- merge(arr)
- return count
- class Solution:
- def inversionCount(self, arr, n):
- global count
- count=0
- def merge(arr):
- if len(arr)>1:
- global count
- mid=len(arr)//2
- L=arr[:mid]
- R=arr[mid:]
- merge(L)
- merge(R)
- m,n=len(L),len(R)
- i=j=0
- while i<m and j<n:#currently i and j are pointing to L,R
- if L[i]<=R[j]:
- '''
- Since we didnt find any inversion here , to get inversion pair we shall increment smaller one.
- i.e. i=i+1 . This is the same case down too. Just increase the smallest ones index.
- '''
- i=i+1
- else:
- '''
- Here you found L[i]>R[j] . Since R is sorted .all the numbers
- from 0....j are are less than L[i].
- Indirectly there are (m-i) inversion pairs. now here which is smaller?
- R[j] so increment that index i.e. j.
- '''
- count+=(m-i)
- j=j+1
- '''
- Now even if i is not eq to m or j is not eq n doesnt matter we have counted
- all inv pairs. Now just merge
- '''
- i=j=k=0
- #now do merge operation
- while i<m and j<n:
- if L[i]<R[j]:
- arr[k]=L[i]
- i=i+1
- else:
- arr[k]=R[j]
- j=j+1
- k=k+1
- while i<m:
- arr[k]=L[i]
- k=k+1
- i=i+1
- while j<n:
- arr[k]=R[j]
- k=k+1
- j=j+1
- merge(arr)
- return count
Advertisement
Add Comment
Please, Sign In to add comment