计算数组中的索引总数对，使得arr [i] <arr [j]和i <j

Question

想要问这个here，但由于我忘记提及索引的条件，因此创建了一个新问题。

该问题给出了一个未排序的数组，找到指数对的总数i, j，例如i < j和arr[i] < arr[j]。复杂性应该是线性的或者与其接近。

Answer 1

如果目标是找到对i < j使得arr[i] > arr[j]的数目，这将是反转次数，能够通过合并排序的阵列和计数每个项目多少个值移动经过来确定。

在这里，如果按降序排列，我们也可以这样做。

int pairs_count(int[] arr, int lo, int hi) { 
    if (hi <= lo) return 0; 
    int mid = (lo+hi)/2; 
    int count = pairs_count(arr, lo, mid); 
    count += pairs_count(arr, mid+1,hi); 
    count += merge(arr, lo, mid, hi); 
    return count; 
} 

int merge(int[] arr, int lo, int mid, int hi) { 
    int[] scratch = new int[hi-lo+1]; 
    int l = lo, r = mid+1, k = 0, count = 0; 
    while(l <= mid && r <= hi) { 
     if (arr[r] > arr[l]) { 
      scratch[k++] = arr[r++]; 
      count += mid-l+1; 
     } else { 
      scratch[k++] = arr[l++]; 
     } 
    } 
    while(l <= mid) { 
     scratch[k++] = arr[l++]; 
    } 
    while(r <= hi) { 
     scratch[k++] = arr[r++]; 
    } 
    for(k = 0; k < scratch.length; ++k) { 
     arr[lo+k] = scratch[k]; 
    } 
    retrun count; 
} 

用pairs_count(arr, 0, arr.length - 1);与之联系。