倒計數（大輸入問題）

Question

我目前正在使用mergesort進行倒計數練習。我面臨的問題是當我有小型或中型陣列時，結果非常好，但如果我使用非常大的測試用例（100,000個整數數組），它不會給我正確的反轉次數。我不知道爲什麼會發生這種情況。這裏是我的代碼：

static int [] helper; 
static long count=0; 
static Integer [] arr3; 

private static void mergeSortMethod(Integer[] arr3) { 
    int head=0; 
    int tail=arr3.length-1; 
    int mid=tail+((head-tail)/2); 

    sort(arr3,head,tail); 
} 


private static void sort(Integer[] arr3, int low, int high) { 

    if (high<=low){ 
     return; 
    } 
    int mid=low+ ((high-low)/2); 

    sort(arr3,low,mid); 
    sort(arr3,mid+1,high); 

    merge3CountInvs(arr3,low,mid,high); 

} 

private static void merge3CountInvs(Integer[] arr3, int low, int mid, int high) { 
    int i=low; 
    int j=mid+1; 
    int k=low; 
    //to get size of first half of array 
    int nArr1Elems=(mid-low)+1; 

    for (int m=low;m<=high;m++){ 
     helper[m]=arr3[m]; 

    } 

    while(i < mid+1 && j < high+1){// neither array empty 
     if(helper[i] < helper[j]){ 
      arr3[k++] = helper[i++]; 

     } 

     else if (helper[j] < helper[i]){ 
      arr3[k++] = helper[j++]; 
      int numOFElements=nArr1Elems-i; 
      count=count+(nArr1Elems-i); 

     } 
    } 
    while(i < mid+1){ // arrayB is empty, 
     arr3[k++] = helper[i++]; 
    } 

    while(j < high+1){ // arrayA is empty, 
     arr3[k++] = helper[j++]; 
    } 

} 

不使用非常大的輸入時，但是當我使用的，這是倒我的編號達到100,000整數測試用例我的解決方案提供了正確答案：

從我的實現： - 30588581433

正確答案是：2407905288個

任何想法？我將不勝感激任何形式的幫助。謝謝。

編輯： 正如在關於整數溢出情況的答案中提到的，這是我難以理解的一點，因爲導致溢出的變量「count」被初始化爲「long」，因此應該沒有溢出這個案例。我想不出任何其他變量會導致我的代碼中的整數溢出。非常感謝。

UPDATE：

有沒有相關的整數溢出，但感謝然而雷迪的答案都指向我到正確的方向，再次感謝答案的問題。在我的算法唯一的錯誤是：

int nArr1Elems=(mid-low)+1; 

count=count+(nArr1Elems-i); 

當它應該是：

count=count+(mid-i+1); 

正如我們從留在陣列的左側的元素減去排序最初沒有當「後」由於索引在排序後發生變化，子程序被調用。我寫在我的情況下更新的代碼是否有人會在一個類似的問題，最終成爲我的：

static int [] helper; 
static long count=0; 
static Integer [] arr3; 

private static void mergeSortMethod(Integer[] arr3) { 
    int head=0; 
    int tail=arr3.length-1; 
    int mid=tail+((head-tail)/2); 

    sort(arr3,head,tail); 
} 


private static void sort(Integer[] arr3, int low, int high) { 

    if (high<=low){ 
     return; 
    } 
    int mid=low+ ((high-low)/2); 

    sort(arr3,low,mid); 
    sort(arr3,mid+1,high); 

    merge3CountInvs(arr3,low,mid,high); 

} 

private static void merge3CountInvs(Integer[] arr3, int low, int mid, int high) { 
    int i=low; 
    int j=mid+1; 
    int k=low; 

    for (int m=low;m<=high;m++){ 
     helper[m]=arr3[m]; 

    } 

    while(i < mid+1 && j < high+1){// neither array empty 
     if(helper[i] < helper[j]){ 
      arr3[k++] = helper[i++]; 

     } 

     else if (helper[j] < helper[i]){ 
      arr3[k++] = helper[j++]; 
     //to increment count with total number of elements left in arrayA after sorting 
      count=count+(mid-i+1); 

     } 
    } 
    while(i < mid+1){ // arrayB is empty, 
     arr3[k++] = helper[i++]; 
    } 

    while(j < high+1){ // arrayA is empty, 
     arr3[k++] = helper[j++]; 
    } 

} 

Answer 1

我的代碼對你的數據工作正常，我得到了完美的結果。 請與它比較，並檢查你在算法

public static void main(String[] args){ 
      int[] dataInv = new int[100000]; 
      Random rand = new Random(); 
      for (int i = 0; i < dataInv.length; i++) { 
       dataInv[i] = rand.nextInt(); 
      } 

      System.out.println("Inversions: " + numberOfInversions(dataInv)); 
    } 

    private static long numberOfInversions(int[] data) { 
     int[] temp = new int[data.length]; 
     return mergeSort(data, temp, 0, data.length - 1); 
    } 

    private static long mergeSort(int[] data, int[] temp, int low, int high) { 
     long inversions = 0L; 
     if (high > low) { 

      int mid = (high + low)/2; 

      inversions = mergeSort(data, temp, low, mid); 
      inversions += mergeSort(data, temp, mid + 1, high); 

      inversions += merge(data, temp, low, mid + 1, high); 
     } 

     return inversions; 
    } 

    private static long merge(int[] data, int[] temp, int low, int mid, int high) { 
     int i, j, k = 0; 
     long invertions = 0L; 

     i = low; 
     j = mid; 
     k = low; 

     while (i <= (mid - 1) && j <= high) { 
      if (data[i] <= data[j]) { 
       temp[k++] = data[i++]; 
      } else { 
       temp[k++] = data[j++]; 

       invertions += (mid - i); 
      } 
     } 

     while (i <= (mid - 1)) { 
      temp[k++] = data[i++]; 
     } 

     while (j <= high) { 
      temp[k++] = data[j++]; 
     } 

     for (i = low; i <= high; i++) { 
      data[i] = temp[i]; 
     } 

     return invertions; 

    } 

Answer 2

你試圖存儲數量超過Integer.MAX_VALUE更大 - 嘗試使用long代替

Answer 3

你正在使用不符合32位整數的數字，因此您有溢出。對於小於2^63或java.math.BigInteger的結果，使用long表示適合您的記憶的所有可能整數。

Answer 4

想一想：假設你在子數組中調用sort（），其中low = 99990和high = 99999。然後mid = 99994。在merge3CountInvs（）中，nArr1Elems是什麼？ 「我」會採取什麼樣的價值觀？在聲明中將加入什麼數字

 count=count+(nArr1Elems-i); 

？