计数数组中的倒数
我正在设计一个算法来执行以下操作：给定数组A[1... n] ，对于每个i < j ，找到所有的反转对，使得A[i] > A[j] 。 我正在使用合并排序和复制数组A到数组B，然后比较这两个数组，但我很难看到我可以如何使用这个找到倒数的数目。 任何提示或帮助将不胜感激。
我可以给这个（唯一的建议是看起来像一个家庭作业问题）的唯一的建议是，首先手动使用一小组数字（例如5），然后写下你解决问题的步骤。
这应该让你找出一个你可以用来编写代码的通用解决方案。
所以这里是java中的O（n log n）解决方案。
long merge(int[] arr, int[] left, int[] right) { int i = 0, j = 0, count = 0; while (i < left.length || j < right.length) { if (i == left.length) { arr[i+j] = right[j]; j++; } else if (j == right.length) { arr[i+j] = left[i]; i++; } else if (left[i] <= right[j]) { arr[i+j] = left[i]; i++; } else { arr[i+j] = right[j]; count += left.length-i; j++; } } return count; } long invCount(int[] arr) { if (arr.length < 2) return 0; int m = (arr.length + 1) / 2; int left[] = Arrays.copyOfRange(arr, 0, m); int right[] = Arrays.copyOfRange(arr, m, arr.length); return invCount(left) + invCount(right) + merge(arr, left, right); }
这几乎是正常的合并排序，整个魔法隐藏在合并函数中。 请注意，虽然排序算法删除倒置。 合并算法计算移除的倒数的数量（可以这样说）。
只有当算法从数组的右侧取元素并将其合并到主数组时，唯一的一次移除倒数的时候。 此操作移除的反转次数是左数组中要合并的元素的数量。 🙂
希望这是足够的解释。
我已经通过以下方法在O（n * log n）时间中找到了它。
- 合并排序数组A并创建一个副本（数组B）
-
取A [1]并通过二分搜索在排序后的数组B中找到它的位置。 因为在A的第一个元素之后出现的每个较低的数字将是反转，所以该元素的反转次数将比它在B中的位置的索引号小1。
2A。 累加反转次数来计数变量num_inversions。
2B。 从数组A中移除A [1]，也从数组B中的相应位置移除
- 从步骤2重新运行，直到A中没有更多的元素。
下面是这个算法的一个例子。 原始数组A =（6,9,1，14，8，12，3，2）
1：合并排序并复制到数组B中
B =（1，2，3，6，8，9，12，14）
2：采取A [1]和二进制搜索在阵列B中找到它
A [1] = 6
B =（1，2，3，6，8，9，12，14）
6位于B组的第4位，因此有3位反转。 我们知道这是因为6在数组A中的第一个位置，因此随后出现在数组A中的任何较低值的元素将具有j> i的索引（因为在这种情况下为1）。
2.b：从数组A中删除A [1]，也从数组B中相应的位置删除（删除了粗体元素）。
A =（ 6,9,1，14,8,12,3,2 ）=（9,1，14，8，12，3，2）
B =（1，2，3，6，8，9，12，14）=（1，2，3，8，9，12，14）
3：从新的A和B阵列的第2步重新运行。
A [1] = 9
B =（1，2，3，8，9，12，14）
现在9位在B位的第5位，因此有4位反转。 我们知道这是因为9在数组A中处于第一位置，因此随后出现的任何较低值的元素将具有j> i的索引（因为在这种情况下我再次是1）。 从数组A中删除A [1]，也从数组B中相应的位置删除（删除了粗体元素）
A =（ 9,1,14,8,12,3,2 ）=（1，14，8，12，3，2）
B =（1,2,3，8，9，12，14）=（1,2,3，8,12,14）
继续这样的情况下，一旦循环完成，将给我们阵列A的反转总数。
步骤1（合并排序）将执行O（n * log n）。 步骤2将执行n次，每次执行都会执行一个二进制搜索，使O（log n）总共运行O（n * log n）。 总运行时间因此是O（n * log n）+ O（n * log n）= O（n * log n）。
谢谢你的帮助。 将样本数组写在一张纸上确实有助于将问题形象化。
在Python中
# O(n log n) def count_inversion(lst): return merge_count_inversion(lst)[1] def merge_count_inversion(lst): if len(lst) <= 1: return lst, 0 middle = int( len(lst) / 2 ) left, a = merge_count_inversion(lst[:middle]) right, b = merge_count_inversion(lst[middle:]) result, c = merge_count_split_inversion(left, right) return result, (a + b + c) def merge_count_split_inversion(left, right): result = [] count = 0 i, j = 0, 0 left_len = len(left) while i < left_len and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) count += left_len - i j += 1 result += left[i:] result += right[j:] return result, count #test code input_array_1 = [] #0 input_array_2 = [1] #0 input_array_3 = [1, 5] #0 input_array_4 = [4, 1] #1 input_array_5 = [4, 1, 2, 3, 9] #3 input_array_6 = [4, 1, 3, 2, 9, 5] #5 input_array_7 = [4, 1, 3, 2, 9, 1] #8 print count_inversion(input_array_1) print count_inversion(input_array_2) print count_inversion(input_array_3) print count_inversion(input_array_4) print count_inversion(input_array_5) print count_inversion(input_array_6) print count_inversion(input_array_7)
实际上，我有一个类似于这个作业的问题。 我受到限制，它必须有O（nlogn）的效率。
我用你提出的使用Mergesort的想法，因为它已经是正确的效率了。 我只是在合并函数中插入了一些代码，这个函数基本上是这样的：只要右边数组中的数字被添加到输出数组中，我就添加了反转的总数，左边数组中剩余的数字。
现在我已经想好了，这对我来说很有意义。 你数了多少次数之前有更多的数字。
心连心。
我想知道为什么没有人提到二进制索引树 。 您可以使用一个维护您的排列元素的值的前缀总和。 然后，您可以从右到左进行计算，每个元素的数量比右边的要小。
def count_inversions(a): res = 0 counts = [0]*(len(a)+1) rank = { v : i+1 for i, v in enumerate(sorted(a)) } for x in reversed(a): i = rank[x] - 1 while i: res += counts[i] i -= i & -i i = rank[x] while i <= len(a): counts[i] += 1 i += i & -i return res
复杂度为O（n log n），常数因子很低。
请注意，杰弗里·欧文的答案是错误的。
数组中的反转次数是总距离的一半，为了对数组进行排序，元素必须被移动。 因此，可以通过对数组进行排序，保持得到的置换p [i]，然后计算abs（p [i] -i）/ 2的和来计算它。 这需要O（n log n）时间，这是最佳的。
http://mathworld.wolfram.com/PermutationInversion.html提供了一种替代方法。; 这个方法相当于max（0，p [i] -i）的总和，它等于abs（p [i] -i]）/ 2之和，因为总距离元素向左移动等于总距离元素向右移动。
以序列{3，2，1}为例。 有3个反演：（3,2），（3,1），（2,1），所以反演数是3.然而，根据引用的方法，答案将是2。
通过分析合并排序中的合并过程可以找到反转次数： 
将第二个数组中的元素复制到合并数组（本例中为9）时，它相对于其他元素保持其位置。 当从第一个数组复制一个元素到合并数组（这里是5）时，它将与所有停留在第二个数组中的元素相反（2和3和4反转）。 所以对合并排序的一些修改可以解决O（n ln n）中的问题。
例如，取消注释下面的mergesort python代码中的两个＃行来计数。
def merge(l1,l2): l = [] # global count while l1 and l2: if l1[-1] <= l2[-1]: l.append(l2.pop()) else: l.append(l1.pop()) # count += len(l2) l.reverse() return l1 + l2 +l def sort(l): t = len(l) // 2 return merge(sort(l[:t]), sort(l[t:])) if t > 0 else l count=0 print(sort([5,1,2,4,9,3]), count) # [1, 2, 3, 4, 5, 9] 6
看看这个： http : //www.cs.jhu.edu/~xfliu/600.363_F03/hw_solution/solution1.pdf
我希望它会给你正确的答案。
- 2-3反转部分（d）
- 它的运行时间是O（nlogn）
这是一个二叉树变种的可能解决方案。 它为每个树节点添加一个名为rightSubTreeSize的字段。 继续按照它们在数组中出现的顺序将数字插入到二叉树中。 如果数字变为节点的lhs，则该元素的反转计数将是（1 + rightSubTreeSize）。 由于所有这些元素都大于当前元素，并且它们会在数组中更早出现。 如果元素转到节点的rhs，只需增加其右边的SubTreeSize即可。 以下是代码。
Node { int data; Node* left, *right; int rightSubTreeSize; Node(int data) { rightSubTreeSize = 0; } }; Node* root = null; int totCnt = 0; for(i = 0; i < n; ++i) { Node* p = new Node(a[i]); if(root == null) { root = p; continue; } Node* q = root; int curCnt = 0; while(q) { if(p->data <= q->data) { curCnt += 1 + q->rightSubTreeSize; if(q->left) { q = q->left; } else { q->left = p; break; } } else { q->rightSubTreeSize++; if(q->right) { q = q->right; } else { q->right = p; break; } } } totCnt += curCnt; } return totCnt;
public static int mergeSort(int[] a, int p, int r) { int countInversion = 0; if(p < r) { int q = (p + r)/2; countInversion = mergeSort(a, p, q); countInversion += mergeSort(a, q+1, r); countInversion += merge(a, p, q, r); } return countInversion; } public static int merge(int[] a, int p, int q, int r) { //p=0, q=1, r=3 int countingInversion = 0; int n1 = q-p+1; int n2 = rq; int[] temp1 = new int[n1+1]; int[] temp2 = new int[n2+1]; for(int i=0; i<n1; i++) temp1[i] = a[p+i]; for(int i=0; i<n2; i++) temp2[i] = a[q+1+i]; temp1[n1] = Integer.MAX_VALUE; temp2[n2] = Integer.MAX_VALUE; int i = 0, j = 0; for(int k=p; k<=r; k++) { if(temp1[i] <= temp2[j]) { a[k] = temp1[i]; i++; } else { a[k] = temp2[j]; j++; countingInversion=countingInversion+(n1-i); } } return countingInversion; } public static void main(String[] args) { int[] a = {1, 20, 6, 4, 5}; int countInversion = mergeSort(a, 0, a.length-1); System.out.println(countInversion); }
这是c ++解决方案
/** *array sorting needed to verify if first arrays n'th element is greater than sencond arrays *some element then all elements following n will do the same */ #include<stdio.h> #include<iostream> using namespace std; int countInversions(int array[],int size); int merge(int arr1[],int size1,int arr2[],int size2,int[]); int main() { int array[] = {2, 4, 1, 3, 5}; int size = sizeof(array) / sizeof(array[0]); int x = countInversions(array,size); printf("number of inversions = %d",x); } int countInversions(int array[],int size) { if(size > 1 ) { int mid = size / 2; int count1 = countInversions(array,mid); int count2 = countInversions(array+mid,size-mid); int temp[size]; int count3 = merge(array,mid,array+mid,size-mid,temp); for(int x =0;x<size ;x++) { array[x] = temp[x]; } return count1 + count2 + count3; }else{ return 0; } } int merge(int arr1[],int size1,int arr2[],int size2,int temp[]) { int count = 0; int a = 0; int b = 0; int c = 0; while(a < size1 && b < size2) { if(arr1[a] < arr2[b]) { temp[c] = arr1[a]; c++; a++; }else{ temp[c] = arr2[b]; b++; c++; count = count + size1 -a; } } while(a < size1) { temp[c] = arr1[a]; c++;a++; } while(b < size2) { temp[c] = arr2[b]; c++;b++; } return count; }
这是一个计数倒数的C代码
#include <stdio.h> #include <stdlib.h> int _mergeSort(int arr[], int temp[], int left, int right); int merge(int arr[], int temp[], int left, int mid, int right); /* This function sorts the input array and returns the number of inversions in the array */ int mergeSort(int arr[], int array_size) { int *temp = (int *)malloc(sizeof(int)*array_size); return _mergeSort(arr, temp, 0, array_size - 1); } /* An auxiliary recursive function that sorts the input array and returns the number of inversions in the array. */ int _mergeSort(int arr[], int temp[], int left, int right) { int mid, inv_count = 0; if (right > left) { /* Divide the array into two parts and call _mergeSortAndCountInv() for each of the parts */ mid = (right + left)/2; /* Inversion count will be sum of inversions in left-part, right-part and number of inversions in merging */ inv_count = _mergeSort(arr, temp, left, mid); inv_count += _mergeSort(arr, temp, mid+1, right); /*Merge the two parts*/ inv_count += merge(arr, temp, left, mid+1, right); } return inv_count; } /* This funt merges two sorted arrays and returns inversion count in the arrays.*/ int merge(int arr[], int temp[], int left, int mid, int right) { int i, j, k; int inv_count = 0; i = left; /* i is index for left subarray*/ j = mid; /* i is index for right subarray*/ k = left; /* i is index for resultant merged subarray*/ while ((i <= mid - 1) && (j <= right)) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; /*this is tricky -- see above explanation/diagram for merge()*/ inv_count = inv_count + (mid - i); } } /* Copy the remaining elements of left subarray (if there are any) to temp*/ while (i <= mid - 1) temp[k++] = arr[i++]; /* Copy the remaining elements of right subarray (if there are any) to temp*/ while (j <= right) temp[k++] = arr[j++]; /*Copy back the merged elements to original array*/ for (i=left; i <= right; i++) arr[i] = temp[i]; return inv_count; } /* Driver progra to test above functions */ int main(int argv, char** args) { int arr[] = {1, 20, 6, 4, 5}; printf(" Number of inversions are %d \n", mergeSort(arr, 5)); getchar(); return 0; }
在这里详细解释： http : //www.geeksforgeeks.org/counting-inversions/
这里是O（n * log（n））perl实现：
sub sort_and_count { my ($arr, $n) = @_; return ($arr, 0) unless $n > 1; my $mid = $n % 2 == 1 ? ($n-1)/2 : $n/2; my @left = @$arr[0..$mid-1]; my @right = @$arr[$mid..$n-1]; my ($sleft, $x) = sort_and_count( \@left, $mid ); my ($sright, $y) = sort_and_count( \@right, $n-$mid); my ($merged, $z) = merge_and_countsplitinv( $sleft, $sright, $n ); return ($merged, $x+$y+$z); } sub merge_and_countsplitinv { my ($left, $right, $n) = @_; my ($l_c, $r_c) = ($#$left+1, $#$right+1); my ($i, $j) = (0, 0); my @merged; my $inv = 0; for my $k (0..$n-1) { if ($i<$l_c && $j<$r_c) { if ( $left->[$i] < $right->[$j]) { push @merged, $left->[$i]; $i+=1; } else { push @merged, $right->[$j]; $j+=1; $inv += $l_c - $i; } } else { if ($i>=$l_c) { push @merged, @$right[ $j..$#$right ]; } else { push @merged, @$left[ $i..$#$left ]; } last; } } return (\@merged, $inv); }
简单的O（n ^ 2）答案是使用嵌套的for-loops并为每个反转增加一个计数器
int counter = 0; for(int i = 0; i < n - 1; i++) { for(int j = i+1; j < n; j++) { if( A[i] > A[j] ) { counter++; } } } return counter;
现在我想你想要一个更有效的解决方案，我会考虑一下。
由于这是一个老问题，我会在C中提供答案。
#include <stdio.h> int count = 0; int inversions(int a[], int len); void mergesort(int a[], int left, int right); void merge(int a[], int left, int mid, int right); int main() { int a[] = { 1, 5, 2, 4, 0 }; printf("%d\n", inversions(a, 5)); } int inversions(int a[], int len) { mergesort(a, 0, len - 1); return count; } void mergesort(int a[], int left, int right) { if (left < right) { int mid = (left + right) / 2; mergesort(a, left, mid); mergesort(a, mid + 1, right); merge(a, left, mid, right); } } void merge(int a[], int left, int mid, int right) { int i = left; int j = mid + 1; int k = 0; int b[right - left + 1]; while (i <= mid && j <= right) { if (a[i] <= a[j]) { b[k++] = a[i++]; } else { printf("right element: %d\n", a[j]); count += (mid - i + 1); printf("new count: %d\n", count); b[k++] = a[j++]; } } while (i <= mid) b[k++] = a[i++]; while (j <= right) b[k++] = a[j++]; for (i = left, k = 0; i <= right; i++, k++) { a[i] = b[k]; } }
在C ++中满足O（N * log（N））时间复杂度要求的一个可能的解决方案如下。
#include <algorithm> vector<int> merge(vector<int>left, vector<int>right, int &counter) { vector<int> result; vector<int>::iterator it_l=left.begin(); vector<int>::iterator it_r=right.begin(); int index_left=0; while(it_l!=left.end() || it_r!=right.end()) { // the following is true if we are finished with the left vector // OR if the value in the right vector is the smaller one. if(it_l==left.end() || (it_r!=right.end() && *it_r<*it_l) ) { result.push_back(*it_r); it_r++; // increase inversion counter counter+=left.size()-index_left; } else { result.push_back(*it_l); it_l++; index_left++; } } return result; } vector<int> merge_sort_and_count(vector<int> A, int &counter) { int N=A.size(); if(N==1)return A; vector<int> left(A.begin(),A.begin()+N/2); vector<int> right(A.begin()+N/2,A.end()); left=merge_sort_and_count(left,counter); right=merge_sort_and_count(right,counter); return merge(left, right, counter); }
它不同于仅由计数器进行的常规归并排序。
O（n log n）时间，O（n）空间解决方案在java中。
一个mergesort，通过调整来保存合并步骤中执行的反转次数。 （对于一个很好的解释mergesort看看http://www.vogella.com/tutorials/JavaAlgorithmsMergesort/article.html ）
由于可以合并合并，空间复杂度可以提高到O（1）。
当使用这种类型时，反转只发生在合并步骤中，只有当我们不得不在第一部分的元素之前放置第二部分的元素时，例如
- 0 5 10 15
合并
- 1 6 22
我们有3 + 2 + 0 = 5的倒数：
- 1与{5,10,15}
- 6与{10,15}
- 22 {}
我们做了5次倒序之后，我们新的合并名单是0,1,5,6,10,15,22
Codility上有一个名为ArrayInversionCount的演示任务，您可以在其中测试您的解决方案。
public class FindInversions { public static int solution(int[] input) { if (input == null) return 0; int[] helper = new int[input.length]; return mergeSort(0, input.length - 1, input, helper); } public static int mergeSort(int low, int high, int[] input, int[] helper) { int inversionCount = 0; if (low < high) { int medium = low + (high - low) / 2; inversionCount += mergeSort(low, medium, input, helper); inversionCount += mergeSort(medium + 1, high, input, helper); inversionCount += merge(low, medium, high, input, helper); } return inversionCount; } public static int merge(int low, int medium, int high, int[] input, int[] helper) { int inversionCount = 0; for (int i = low; i <= high; i++) helper[i] = input[i]; int i = low; int j = medium + 1; int k = low; while (i <= medium && j <= high) { if (helper[i] <= helper[j]) { input[k] = helper[i]; i++; } else { input[k] = helper[j]; // the number of elements in the first half which the j element needs to jump over. // there is an inversion between each of those elements and j. inversionCount += (medium + 1 - i); j++; } k++; } // finish writing back in the input the elements from the first part while (i <= medium) { input[k] = helper[i]; i++; k++; } return inversionCount; } }
我最近不得不在R：
inversionNumber <- function(x){ mergeSort <- function(x){ if(length(x) == 1){ inv <- 0 } else { n <- length(x) n1 <- ceiling(n/2) n2 <- n-n1 y1 <- mergeSort(x[1:n1]) y2 <- mergeSort(x[n1+1:n2]) inv <- y1$inversions + y2$inversions x1 <- y1$sortedVector x2 <- y2$sortedVector i1 <- 1 i2 <- 1 while(i1+i2 <= n1+n2+1){ if(i2 > n2 || i1 <= n1 && x1[i1] <= x2[i2]){ x[i1+i2-1] <- x1[i1] i1 <- i1 + 1 } else { inv <- inv + n1 + 1 - i1 x[i1+i2-1] <- x2[i2] i2 <- i2 + 1 } } } return (list(inversions=inv,sortedVector=x)) } r <- mergeSort(x) return (r$inversions) }
Java实现：
import java.lang.reflect.Array; import java.util.Arrays; public class main { public static void main(String[] args) { int[] arr = {6, 9, 1, 14, 8, 12, 3, 2}; System.out.println(findinversion(arr,0,arr.length-1)); } public static int findinversion(int[] arr,int beg,int end) { if(beg >= end) return 0; int[] result = new int[end-beg+1]; int index = 0; int mid = (beg+end)/2; int count = 0, leftinv,rightinv; //System.out.println("...."+beg+" "+end+" "+mid); leftinv = findinversion(arr, beg, mid); rightinv = findinversion(arr, mid+1, end); l1: for(int i = beg, j = mid+1; i<=mid || j<=end;/*index < result.length;*/ ) { if(i>mid) { for(;j<=end;j++) result[index++]=arr[j]; break l1; } if(j>end) { for(;i<=mid;i++) result[index++]=arr[i]; break l1; } if(arr[i] <= arr[j]) { result[index++]=arr[i]; i++; } else { System.out.println(arr[i]+" "+arr[j]); count = count+ mid-i+1; result[index++]=arr[j]; j++; } } for(int i = 0, j=beg; i< end-beg+1; i++,j++) arr[j]= result[i]; return (count+leftinv+rightinv); //System.out.println(Arrays.toString(arr)); } }
这是我使用Scala的：
trait MergeSort { def mergeSort(ls: List[Int]): List[Int] = { def merge(ls1: List[Int], ls2: List[Int]): List[Int] = (ls1, ls2) match { case (_, Nil) => ls1 case (Nil, _) => ls2 case (lowsHead :: lowsTail, highsHead :: highsTail) => if (lowsHead <= highsHead) lowsHead :: merge(lowsTail, ls2) else highsHead :: merge(ls1, highsTail) } ls match { case Nil => Nil case head :: Nil => ls case _ => val (lows, highs) = ls.splitAt(ls.size / 2) merge(mergeSort(lows), mergeSort(highs)) } } } object InversionCounterApp extends App with MergeSort { @annotation.tailrec def calculate(list: List[Int], sortedListZippedWithIndex: List[(Int, Int)], counter: Int = 0): Int = list match { case Nil => counter case head :: tail => calculate(tail, sortedListZippedWithIndex.filterNot(_._1 == 1), counter + sortedListZippedWithIndex.find(_._1 == head).map(_._2).getOrElse(0)) } val list: List[Int] = List(6, 9, 1, 14, 8, 12, 3, 2) val sortedListZippedWithIndex: List[(Int, Int)] = mergeSort(list).zipWithIndex println("inversion counter = " + calculate(list, sortedListZippedWithIndex)) // prints: inversion counter = 28 }
I think el diablo's answer can be optimized to remove step 2b in which we delete already processed elements.
Instead we can define
# of inversion for x = position of x in sorted array – position of x in orig array
Another Python solution, short one. Makes use of builtin bisect module, which provides functions to insert element into its place in sorted array and to find index of element in sorted array.
The idea is to store elements left of n-th in such array, which would allow us to easily find the number of them greater than n-th.
Complexity is O(n * log n)
import bisect def solution(A): sorted_left = [] res = 0 for i in xrange(1, len(A)): bisect.insort_left(sorted_left, A[i-1]) # i is also the length of sorted_left res += (i - bisect.bisect(sorted_left, A[i])) return res
C code easy to understand:
#include<stdio.h> #include<stdlib.h> //To print an array void print(int arr[],int n) { int i; for(i=0,printf("\n");i<n;i++) printf("%d ",arr[i]); printf("\n"); } //Merge Sort int merge(int arr[],int left[],int right[],int l,int r) { int i=0,j=0,count=0; while(i<l || j<r) { if(i==l) { arr[i+j]=right[j]; j++; } else if(j==r) { arr[i+j]=left[i]; i++; } else if(left[i]<=right[j]) { arr[i+j]=left[i]; i++; } else { arr[i+j]=right[j]; count+=li; j++; } } //printf("\ncount:%d\n",count); return count; } //Inversion Finding int inversions(int arr[],int high) { if(high<1) return 0; int mid=(high+1)/2; int left[mid]; int right[high-mid+1]; int i,j; for(i=0;i<mid;i++) left[i]=arr[i]; for(i=high-mid,j=high;j>=mid;i--,j--) right[i]=arr[j]; //print(arr,high+1); //print(left,mid); //print(right,high-mid+1); return inversions(left,mid-1) + inversions(right,high-mid) + merge(arr,left,right,mid,high-mid+1); } int main() { int arr[]={6,9,1,14,8,12,3,2}; int n=sizeof(arr)/sizeof(arr[0]); print(arr,n); printf("%d ",inversions(arr,n-1)); return 0; }
Here's my O(n log n) solution in Ruby:
def solution(t) sorted, inversion_count = sort_inversion_count(t) return inversion_count end def sort_inversion_count(t) midpoint = t.length / 2 left_half = t[0...midpoint] right_half = t[midpoint..t.length] if midpoint == 0 return t, 0 end sorted_left_half, left_half_inversion_count = sort_inversion_count(left_half) sorted_right_half, right_half_inversion_count = sort_inversion_count(right_half) sorted = [] inversion_count = 0 while sorted_left_half.length > 0 or sorted_right_half.length > 0 if sorted_left_half.empty? sorted.push sorted_right_half.shift elsif sorted_right_half.empty? sorted.push sorted_left_half.shift else if sorted_left_half[0] > sorted_right_half[0] inversion_count += sorted_left_half.length sorted.push sorted_right_half.shift else sorted.push sorted_left_half.shift end end end return sorted, inversion_count + left_half_inversion_count + right_half_inversion_count end
And some test cases:
require "minitest/autorun" class TestCodility < Minitest::Test def test_given_example a = [-1, 6, 3, 4, 7, 4] assert_equal solution(a), 4 end def test_empty a = [] assert_equal solution(a), 0 end def test_singleton a = [0] assert_equal solution(a), 0 end def test_none a = [1,2,3,4,5,6,7] assert_equal solution(a), 0 end def test_all a = [5,4,3,2,1] assert_equal solution(a), 10 end def test_clones a = [4,4,4,4,4,4] assert_equal solution(a), 0 end end
My answer in Python:
1- Sort the Array first and make a copy of it. In my program, B represents the sorted array. 2- Iterate over the original array (unsorted), and find the index of that element on the sorted list. Also note down the index of the element. 3- Make sure the element doesn't have any duplicates, if it has then you need to change the value of your index by -1. The while condition in my program is exactly doing that. 4- Keep counting the inversion that will your index value, and remove the element once you have calculated its inversion.
def binarySearch(alist, item): first = 0 last = len(alist) - 1 found = False while first <= last and not found: midpoint = (first + last)//2 if alist[midpoint] == item: return midpoint else: if item < alist[midpoint]: last = midpoint - 1 else: first = midpoint + 1 def solution(A): B = list(A) B.sort() inversion_count = 0 for i in range(len(A)): j = binarySearch(B, A[i]) while B[j] == B[j - 1]: if j < 1: break j -= 1 inversion_count += j B.pop(j) if inversion_count > 1000000000: return -1 else: return inversion_count print solution([4, 10, 11, 1, 3, 9, 10])
Well I have a different solution but I am afraid that would work only for distinct array elements.
//Code #include <bits/stdc++.h> using namespace std; int main() { int i,n; cin >> n; int arr[n],inv[n]; for(i=0;i<n;i++){ cin >> arr[i]; } vector<int> v; v.push_back(arr[n-1]); inv[n-1]=0; for(i=n-2;i>=0;i--){ auto it = lower_bound(v.begin(),v.end(),arr[i]); //calculating least element in vector v which is greater than arr[i] inv[i]=it-v.begin(); //calculating distance from starting of vector v.insert(it,arr[i]); //inserting that element into vector v } for(i=0;i<n;i++){ cout << inv[i] << " "; } cout << endl; return 0; }
To explain my code we keep on adding elements from the end of Array.For any incoming array element we find the index of first element in vector v which is greater than our incoming element and assign that value to inversion count of the index of incoming element.After that we insert that element into vector v at it's correct position such that vector v remain in sorted order.
//INPUT 4 2 1 4 3 //OUTPUT 1 0 1 0 //To calculate total inversion count just add up all the elements in output array
Best optimized way will be to solve it through merge sort where will merging itself we can check how many inversions are required by comparing left and right array. Whenever element at left array is greater than element at right array, it will be inversion.
Merge sort Approach :-
Here is the code . Code is exact same as merge sort except code snippet under mergeToParent method where i am counting the inversion under else condition of (left[leftunPicked] < right[rightunPicked])
public class TestInversionThruMergeSort { static int count =0; public static void main(String[] args) { int[] arr = {6, 9, 1, 14, 8, 12, 3, 2}; partition(arr); for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } System.out.println("inversions are "+count); } public static void partition(int[] arr) { if (arr.length > 1) { int mid = (arr.length) / 2; int[] left = null; if (mid > 0) { left = new int[mid]; for (int i = 0; i < mid; i++) { left[i] = arr[i]; } } int[] right = new int[arr.length - left.length]; if ((arr.length - left.length) > 0) { int j = 0; for (int i = mid; i < arr.length; i++) { right[j] = arr[i]; ++j; } } partition(left); partition(right); mergeToParent(left, right, arr); } } public static void mergeToParent(int[] left, int[] right, int[] parent) { int leftunPicked = 0; int rightunPicked = 0; int parentIndex = -1; while (rightunPicked < right.length && leftunPicked < left.length) { if (left[leftunPicked] < right[rightunPicked]) { parent[++parentIndex] = left[leftunPicked]; ++leftunPicked; } else { count = count + left.length-leftunPicked; if ((rightunPicked < right.length)) { parent[++parentIndex] = right[rightunPicked]; ++rightunPicked; } } } while (leftunPicked < left.length) { parent[++parentIndex] = left[leftunPicked]; ++leftunPicked; } while (rightunPicked < right.length) { parent[++parentIndex] = right[rightunPicked]; ++rightunPicked; } } }
Another approach where we can compare the input array with sorted array:- This implementation of Diablo answer. Though this should not be preferred approach as removing the n elements from an array or list is log(n^2).
import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Iterator; import java.util.List; public class TestInversion { public static void main(String[] args) { Integer [] arr1 = {6, 9, 1, 14, 8, 12, 3, 2}; List<Integer> arr = new ArrayList(Arrays.asList(arr1)); List<Integer> sortArr = new ArrayList<Integer>(); for(int i=0;i<arr.size();i++){ sortArr.add(arr.get(i)); } Collections.sort(sortArr); int inversion = 0; Iterator<Integer> iter = arr.iterator(); while(iter.hasNext()){ Integer el = (Integer)iter.next(); int index = sortArr.indexOf(el); if(index+1 > 1){ inversion = inversion + ((index+1)-1); } //iter.remove(); sortArr.remove(el); } System.out.println("Inversions are "+inversion); } }
another Python solution
def inv_cnt(a): n = len(a) if n==1: return a,0 left = a[0:n//2] # should be smaller left,cnt1 = inv_cnt(left) right = a[n//2:] # should be larger right, cnt2 = inv_cnt(right) cnt = 0 i_left = i_right = i_a = 0 while i_a < n: if (i_right>=len(right)) or (i_left < len(left) and left[i_left] <= right[i_right]): a[i_a] = left[i_left] i_left += 1 else: a[i_a] = right[i_right] i_right += 1 if i_left < len(left): cnt += len(left) - i_left i_a += 1 return (a, (cnt1 + cnt2 + cnt))
Maximum number of inversions possible for a list of size n could be generalized by an expression:
maxPossibleInversions = (n * (n-1) ) / 2
So for an array of size 6 maximum possible inversions will equal 15 .
To achieve a complexity of n logn we could piggy back the inversion algorithm on merge sort.
Here are the generalized steps:
- Split the array into two
- Call the mergeSort routine. If the element in the left subarray is greater than the element in right sub array make
inversionCount += leftSubArray.length
而已！
This is a simple example, I made using Javascript:
var arr = [6,5,4,3,2,1]; // Sample input array var inversionCount = 0; function mergeSort(arr) { if(arr.length == 1) return arr; if(arr.length > 1) { let breakpoint = Math.ceil((arr.length/2)); // Left list starts with 0, breakpoint-1 let leftList = arr.slice(0,breakpoint); // Right list starts with breakpoint, length-1 let rightList = arr.slice(breakpoint,arr.length); // Make a recursive call leftList = mergeSort(leftList); rightList = mergeSort(rightList); var a = merge(leftList,rightList); return a; } } function merge(leftList,rightList) { let result = []; while(leftList.length && rightList.length) { /** * The shift() method removes the first element from an array * and returns that element. This method changes the length * of the array. */ if(leftList[0] <= rightList[0]) { result.push(leftList.shift()); }else{ inversionCount += leftList.length; result.push(rightList.shift()); } } while(leftList.length) result.push(leftList.shift()); while(rightList.length) result.push(rightList.shift()); console.log(result); return result; } mergeSort(arr); console.log('Number of inversions: ' + inversionCount);
