反轉計數算法有問題

Question

我寫了一個反轉計數的實現。這是一項正在進行的在線課程。但我得到的輸入是不正確的，根據我的程序有一個正確的語法。我不只是知道是我出了問題 程序下面是我實現

import java.io.*; 

class CountInversions { 
    //Create an array of length 1 and keep expanding as data comes in 

    private int elements[]; 
    private int checker = 0; 

    public CountInversions() { 
     elements = new int[1]; 
     checker = 0; 
    } 

    private boolean isFull() { 
     return checker == elements.length; 
    } 

    public int[] getElements() { 
     return elements; 
    } 

    public void push(int value) { 
     if (isFull()) { 
      int newElements[] = new int[elements.length * 2]; 
      System.arraycopy(elements, 0, newElements, 0, elements.length); 
      elements = newElements; 
     } 
     elements[checker++] = value; 
    } 

    public void readInputElements() throws IOException { 
     //Read input from file and until the very last input 
     try { 
      File f = new File("IntegerArray.txt"); 
      FileReader fReader = new FileReader(f); 
      BufferedReader br = new BufferedReader(fReader); 
      String stringln; 
      while ((stringln = br.readLine()) != null) { 
       push(Integer.parseInt(stringln)); 
      } 
      System.out.println(elements.length); 
      fReader.close(); 
     } catch (Exception e) {//Catch exception if any 
      System.err.println("Error: " + e.getMessage()); 
     } finally { 
//   in.close 
     } 
    } 
     //Perform the count inversion algorithm 
    public int countInversion(int array[],int length){ 
     int x,y,z; 
     int mid = array.length/2 ; 
     int k; 
     if (length == 1){ 
      return 0; 
     }else{ 
      //count Leftinversion and count Rightinversion respectively 
      int left[] = new int[mid]; 
      int right[] = new int[array.length - mid]; 

      for(k = 0; k < left.length;k++){ 
       left[k] = array[k]; 
      } 

      for(k = 0 ;k < right.length;k++){ 
       right[k] = array[mid + k]; 
      } 
      x = countInversion(left, left.length); 
      y = countInversion(right, right.length); 
      int result[] = new int[array.length]; 
      z = mergeAndCount(left,right,result); 

      //count splitInversion 
      return x + y + z; 
     } 
    } 

    private int mergeAndCount(int[] left, int[] right, int[] result) { 
     int count = 0; 
     int i = 0, j = 0, k = 0; 
     int m = left.length, n = right.length; 
     while(i < m && j < n){ 
      if(left[i] < right[j]){ 
       result[k++] = left[i++]; 
      }else{ 
       result[k++] = right[j++]; 
       count += left.length - i; 
      } 
     } 
     if(i < m){ 
      for (int p = i ;p < m ;p++){ 
       result[k++] = left[p]; 
      } 
     } 
     if(j < n){ 
      for (int p = j ;p < n ;p++){ 
       result[k++] = right[p]; 
      } 
     } 
     return count; 
    } 
} 
class MainApp{ 
    public static void main(String args[]){ 
     int count = 0; 
     CountInversions cIn = new CountInversions(); 
     try { 
      cIn.readInputElements(); 
      count = cIn.countInversion(cIn.getElements(),cIn.getElements().length); 
      System.out.println("Number of Inversios: " + count); 

     } catch (IOException ex) { 
      ex.printStackTrace(); 
     } 

    } 
} 

Answer 1

您的代碼工作，如果數組長度爲2（實際上是一個動力，我不知道是否如果它，請參閱下面的第二點）。

當讀取輸入時，在數組大小滿了時將數組大小加倍，但不會將其大小調整爲存儲在checker中的實際讀取的項目數。因此，您的數組長度是2的冪，如果從文件中讀取的int的數量不是2的冪，那麼您的數組的長度過長，其中一些尾隨0元素對應於已分配但未從文件中填充的位置。由於你用數組長度調用countInversions而不是讀取項目的數量，因此這些0也被排序，產生一些虛假的反轉。

讀取輸入後，分配一個新的數組

int[] copy = new int[checker]; 
for(int i = 0; i < checker; ++i) { 
    copy[i] = elements[i]; 
} 
elements = copy; 

複製的元件，並丟棄舊的陣列與錯誤的能力。

在你的算法的另一個問題是，你永遠不改變原來的數組，因爲你分配一個新的數組的合併結果，

int result[] = new int[array.length]; 
z = mergeAndCount(left,right,result); 

所以你合併無序排列，這也可能會扭曲的反轉次數。既然你複製輸入數組到新陣列的一半的遞歸調用，您可以毫無問題把合併結果傳入的數組中，因此與

z = mergeAndCount(left,right,array); 

代替上面兩行獲得方法它實際上對數組進行排序並對倒數進行計數。

Answer 2

這個職位是解決數反轉與Java的問題（除文件閱讀，你已經做OK） - Counting inversions in an array