Last active
February 1, 2016 02:45
-
-
Save sb8244/eff21ba43b27e96a0b8e to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# First sort the input using an nlogn method | |
# Then iterate over the array, finding the index of each value in the sorted array | |
# The index of the value in the sorted array is the inversion count, because all items to the left are less | |
# Sum those up | |
# Be sure to use the most efficient searching and not build in. (nlogn sort and logn search) | |
def solution(a) | |
return 0 if a.empty? | |
sorted = a.sort | |
inversions = a.each_with_index.map do |val, index| | |
index_in_sorted = bin_search(sorted, val) | |
sorted.delete_at(index_in_sorted) | |
index_in_sorted | |
end.reduce(&:+) | |
inversions > 1_000_000_000 ? -1 : inversions | |
end | |
def bin_search(arr, val) | |
bin_search_r(arr, val, 0, arr.count - 1) | |
end | |
def bin_search_r(arr, val, min, max) | |
mid = (max+min)/2 | |
if arr[mid] > val | |
bin_search_r(arr, val, min, mid - 1) | |
elsif arr[mid] < val | |
bin_search_r(arr, val, mid + 1, max) | |
else | |
found_index = mid | |
while(found_index > 0 && arr[found_index-1] == val) | |
found_index -= 1 | |
end | |
found_index | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Credit to https://www.quora.com/How-can-the-number-of-inversions-between-two-arrays-be-calculated-in-O-N-log-N because I wouldn't have known that about inversion count.