java - 查找 k - 最小元素(Java 代码)

Question

我想解决以下问题:给定一个包含 n 个元素的未排序数组，找到前 k 个最小元素。为此，我想构建一个大小为 k 的最大堆(来自数组的最后 k 个元素)，然后扫描数组中的其余元素。如果我找到比我的根元素更小的元素，我会交换这两个元素，然后堆化我的堆。该解决方案应该在 O(nlogk) 时间内有效并且到位。但是我无法修复它(我有索引越界异常)。我尝试调试它，但我不知道我的错误在哪里。这是我的代码:

public class KSmallest {
    private static int[] a;
    private static int n;

    public static void buildheap(int []a){
        n=a.length-1;
        for(int i=n;i>=0;i--){
            maxheap(a,i);
        }
        for (int i = n-1; i >= 0; i--) {
            if(a[i]<a[start]){
                exchange(i, 0);
                maxheap(a, 0);
            }
        }
    }

    public static void exchange(int i, int j){
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }

    public static void sort(int []a0){
        a=a0;
        for(int i=n; i>0; i--){
            exchange(0, i);
            n=n-1;
            maxheap(a, 0);
        }
    }

    public static void main(String[] args) {
        int []a1={4,1,3,2,7, 2, 1, 4};
        int start = a1.length-k;
        for(int i=start;i<a1.length;i++){
            System.out.print(a1[i] + " ");
        }
        System.out.println();
        //sort(a1);
        for(int i=start;i<a1.length;i++){
            System.out.print(a1[i] + " ");
        }
    }
}

我已经为此苦苦挣扎了两天，希望有人能帮忙。

Answer 1

首先要注意的是那些意义不大的变量名称...'a'、'a0'、'i'、'j'、'k'、'n'、't' 以及作为可变的静态变量，使用起来总是一场噩梦。

无论如何，我运行了代码并在 Exchange() 方法中得到了 NullPointerException。

发生的情况是 buildheap() 方法有一个名为“a”的参数，该参数与类变量使用的名称相同，因此当它将“a”传递给 maxheap() 然后 exhange() 时，它传递的是类变量而不是参数。

尝试将此行添加为 buildheap() 方法中的第一行:

KSmallest.a = a;

编辑 我不确定这是否真的有效，但它可以防止 NPE。

为所有变量使用有意义的名称，例如使用“左”、“右”、“最大”等，将会有很大帮助，一些额外的字符不会浪费树木!

也尽量避免可变的静态变量。要么使用“final”关键字将它们保留为常量，然后按照约定将它们全部大写。或者使用实例变量并删除 static 关键字，这是更 OOP 的范例。

无论如何，祝你好运! :)