Short Problem Definition:
Compute number of inversion in an array.
Link
Complexity:
expected worst-case time complexity is O(N*log(N));
expected worst-case space complexity is O(N)
Execution:
Any sorting algorithm with a NlogN runtime will do the trick. It is important to count all (remaining) bigger elements on the left side. Do not forget to check for the maximal return value!
Solution:
MAX_NR = 1000000000 def mergeSort(alist): inversion_count = 0 if len(alist)>1: mid = len(alist)//2 lefthalf = alist[:mid] righthalf = alist[mid:] inversion_count += mergeSort(lefthalf) if (inversion_count > MAX_NR): raise inversion_count += mergeSort(righthalf) if (inversion_count > MAX_NR): raise i=0 j=0 k=0 while i<len(lefthalf) and j<len(righthalf): if lefthalf[i]<=righthalf[j]: alist[k]=lefthalf[i] i=i+1 else: alist[k]=righthalf[j] j=j+1 inversion_count += len(lefthalf)-i if (inversion_count > MAX_NR): raise k=k+1 while i<len(lefthalf): alist[k]=lefthalf[i] i=i+1 k=k+1 while j<len(righthalf): alist[k]=righthalf[j] j=j+1 k=k+1 return inversion_count def solution(A): try: return mergeSort(A) except: return -1
If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.




