How to find the number of inversions in an array ?
It is actually an application of divide-and-conquer algorithm, and if you are familiar with it you can come up with the solution quickly.
Take [1 3 8 5 7 2 4 6] as an example, assume we have sorted array as [1 3 5 8] and [2 4 6 7], and now we need to combine the two arrays and get the number of total inversions.
Since we already have number of inversions in each sub-array, we only need to find out the number of inversions caused by array merging. Each time an element is inserted, for example, 2 inserted into [1 # 3 5 8], you can know how many inversions there are between the first array and the element 2 (3 pairs in this example). Then you can add them up to get the number of inversions caused by merging.
You could also use a counting sort-like approach, if the array only contains small numbers for example (like if it's a character array):
inversions = 0 let count = array of size array.Length for i = 0 to array.Length - 1 do for j = array[i] + 1 to maxArrayValue do inversions = inversions + count[j] count[array[i]] = count[array[i]] + 1
Basically, keep a count of how many times each element appears. Then at each step
i, the number of inversions the
ith element generates is equal to the sum of all the elements bigger than
i that come before
i, which you can easily compute using the count you're keeping.
This will be
eps is the domain of the elements in your array.
This is definitely simpler in my opinion. As for efficiency, it's only good if
eps is small obviously. If it is, then it should be faster than other approaches since there's no recursion.
Related videos on Youtube
Michael 15 days
Counting inversions in an array
This is an phone interview question: "Find the number of inversions in an array". I guess they mean O(Nlog N) solution. I believe it cannot be better than O(Nlog N) since this is the sorting complexity.
The answers to a similar question can be summarized as follows:
Calculate half the distance the elements should be moved to sort the array : copy the array and sort the copy. For each element of the original array
a[i]find it's position
jin the sorted copy (binary search) and sum the halves the distances
abs(i - j)/2.
merge sort: modify
mergeto count inversions between two sorted arrays and run regular
merge sortwith that modified
Does it make sense ? Are there other (maybe simpler) solutions ? Isn't it too hard for a phone interview ?
Marek Kirejczyk about 10 yearsYou can find n log n solution coded in java here: stackoverflow.com/questions/337664/…
huzefa biyawarwala over 1 year@ZelluX - How can we solve for array with duplicate values as
[1, 3, 4, 5, 6, 4]using merge sort ?