得到k - 最小元素（Java的code） [英] Find k - smallest element (Java code)

问题描述

我要解决以下问题：给定n个元素的排序的数组，找到前k个最小的元素。要做到这一点，我想建立大小为k的最大堆（从阵列的最后k个元素），然后以扫描数组中的元素的其余部分。如果我发现一个更小的元素比我的根元素我都交换的元素，然后我heapify我堆。这个解决方案应该O（nlogk）的时间和到位的作品。不过，我不能修复它（我有指数走出束缚例外）。我试图调试，但我看不出哪里是我的错误。这是我的code：

I want to solve the following problem: Given an unsorted array of n elements, find the first k smallest elements. To do this I want to build a max heap of size k (from the last k elements of the array) and then to scan the rest of the elements in the array. If I find a smaller element than my root element I exchange both elements and then I heapify my heap. This solution should works in O(nlogk) time and in place. However I cannot fix it (I have index out of bound exception). I tried to debug it but I don't see where is my mistake. This is my code:

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] + " ");
        }
    }
}

我这个苦苦挣扎了两天，所以我希望有人可以帮助。

I'm struggling with this for two days so I hope anyone can help.

推荐答案

编写堆数据strucutre是一个很好的做法。我使用的优先级队列这是现成的最小堆在java中。对于这个问题，我需要一个最大堆，所以我使用的是比较创建一个最大堆。

Writing the heap data strucutre is a good practice. I am using priority queue which is readily available min Heap in java. for this problem I need a max heap so I am using a Comparator to create a max heap.

public class KLowestElements {

/*comparator to create max heap*/
static class MaxHeapComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer a, Integer b) {
        return b.compareTo(a);
    }
}

public static void main(String[] args) {
    //sample input
    int[] input = { 11, 2, 23, 34, 5};

    // heap size
    int k = 3;
    MaxHeapComparator maxHeapComparator = new MaxHeapComparator();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k,
            maxHeapComparator);

     //Loop Invariant: If heap size is k, compare top element with next 
     //element in the array. If element is smaller than the top element, 
     //remove the top integer and insert element from array. 
     for (int i = 0; i < input.length; i++) {
        if (maxHeap.size() < k) {
            maxHeap.add(input[i]);
        } else if (maxHeap.peek() > input[i]) {
            maxHeap.remove();
            maxHeap.add(input[i]);
        }
    }

    //print values 
    for (int i : maxHeap) {
        System.out.print(i + " ");
    }
}
}

这篇关于得到k - 最小元素（Java的code）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！