反转计数算法有问题

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