任务：
你有一个未排序的元素列表，在我们的例子中是整数，你必须找到该列表中第 k 个最小的元素。显而易见的想法当然是按升序对列表进行排序并返回第k个最小的元素。这应该在 O(N Log N) 中完成。
我试图找到我使用最大堆的第 k 个最小元素。据我了解，我需要按递增顺序对数组进行排序，并在获得第 k 个最小元素时返回。如果我理解正确，最大堆最好用于按递增顺序对数组进行排序，但最小堆用于查找第 k 个最小元素。这是不明白的地方。如何按升序对数组进行排序并返回第 k 分钟？如果我使用最大堆，我在找出如何获得第 k 个最小元素时遇到问题，因为等待数组完全排序是没有意义的，然后用 for 循环遍历它并获得第 k 个最小元素，因为不会使 HeapSort O(N log N) 因为它需要另一个 for 循环来遍历数组。如果我使用最小堆，它将是降序的。
这是最大堆如何按递增顺序对数组进行排序：
最大堆制作：[10, 9, 8, 5, 1, 8, 3, 5, 5, 1]
[9, 5, 8, 5, 1, 8, 3, 1, 5, 10]
[8, 5, 8, 5, 1, 5, 3, 1, 9, 10]
[8, 5, 5, 5, 1, 1, 3, 8, 9, 10]
[5, 5, 5, 3, 1, 1, 8, 8, 9, 10]
[5, 3, 5, 1, 1, 5, 8, 8, 9, 10]
[5, 3, 1, 1, 5, 5, 8, 8, 9, 10]
[3, 1, 1, 5, 5, 5, 8, 8, 9, 10]
[1, 1, 3, 5, 5, 5, 8, 8, 9, 10]
[1, 1, 3, 5, 5, 5, 8, 8, 9, 10]
我不知道如何获得第 k 个最小的。我虽然关于最小堆，因为最小的总是索引 0，但它用于制作递减数组？
这是我的方法，它是一个堆排序。它调用 buildHeap，然后进行排序。
//Find kth smallest element-----------------------------------------------------------------------------------------
private int[] findKthSmallestElement(int[] arr, int kthElement) {
buildheap(arr);
System.out.println("Max Heap is made: " + Arrays.toString(arr));
if(kthElement > arr.length){
System.out.println("Number does not exist.");
return arr;
}
else if(kthElement == arr.length){
System.out.println(kthElement + " st/nd/th smallest element number" + " is: " + arr[0]);
return arr;
}
heapSize = arr.length - 1;
for(int i = heapSize; i > 0; i--) {
swapCurrentNodeWithMaxChild(arr,0, i);
heapSize--;
percolateDown(arr, 0,heapSize);
System.out.println(Arrays.toString(arr));
}
return arr;
}
我试图在最大堆中找到第 k 个最小的元素。据我了解，我需要按递增顺序对数组进行排序，并在获得第 k 个最小元素时返回。
不，要在最大堆中找到第 k 个小元素，我们只需n-k要从最大堆中提取元素。不需要排序。
这不会使 HeapSort O(N log N) 因为它需要另一个 for 循环来遍历数组。
我们不需要对数组进行排序，但作为旁注，遍历数组的循环不会改变任何东西，因为 O(N log N + N) == O(N log N)
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句