java - 反转计数算法有问题

Question

我编写了反转计数的实现。这是在线类(class)中进行的作业。但我得到的输入不正确，根据我所掌握的内容，程序具有正确的语法。我不知道我是否做错了下面的程序是我的实现

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 code> 元素对应于文件中已分配但未填充的位置。由于您使用数组的长度而不是读取的项目数调用 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);

获取实际对数组进行排序并计算反转次数的方法。