計算數組中的索引總數對，使得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);與之聯繫。