【剑指offer-Java版】30最小的K个数

忘是亡心i 2022-08-21 09:47 166阅读 0赞

最小的K个数：  
思路一：类似于第29题，直接进行Partion，直到返回值未K – 缺点是需要修改输入的数据  
思路二：维护一个大顶堆，然后遍历一次给定数组  
如果当前堆元素小于K个  
那么直接将当前元素加入堆中，并调整堆  
如果当前堆中元素等于K个  
如果当前遍历数据小于堆顶元素，那么删除堆顶然后将当前元素插入堆，并调整堆  
如果当前遍历元素大于堆顶，那么什么也不做  
由于建立堆和调整堆的大小的时间复杂度都是logK,而且整个过程只需要遍历一遍数组，因此时间复杂度是O(N\*logK)  
ps:这个堆可以自己实现，不足一百行代码，更简单的，也可以直接使用简易堆，只拥有建立和调整两个操作

public class _Q30<T> {
        
    
        public int[] GetLeastNumbers(int array[], int k){
            if(array == null || k < 0 || k >= array.length) return null;
    
            int result[] = Arrays.copyOfRange(array, 0, k);
            buildMaxHeap(result);
    
            for(int i=k; i<array.length; i++){
                if(array[i] < result[0]){
                    result[0] = array[i];
                    maxHeapify(result, 0);
                }
            }
    
            return result;
        }
    
        private void buildMaxHeap(int heap[]){
    
            if(heap == null) return;
    
            for(int i=(heap.length/2); i>=0; i--){
                maxHeapify(heap, i);
            }
    
        }
    
        // 保持堆的性质：将较小元素逐渐下沉至叶子节点
        private void maxHeapify(int heap[], int index){
            if(heap == null || index < 0) return;
            if(index >= heap.length) return;
    
            int indexL = 2*index + 1;
            int indexR = indexL + 1;
            int largestIndex = index;
    
            if(indexL < heap.length && heap[indexL] > heap[index]){
                largestIndex = indexL;
            }
    
            if(indexR < heap.length && heap[indexR] > heap[index]){
                largestIndex = indexR;
            }
    
            if(largestIndex != index){
                int temp = heap[largestIndex];
                heap[largestIndex] = heap[index];
                heap[index] = temp;
    
                maxHeapify(heap, largestIndex); // 由于调整之后，可能破坏了子结构，递归调整
            }
        }
        }

测试代码：

public class _Q30Test extends TestCase {
        
    
        _Q30 topK = new _Q30();
    
        public void test(){
            int nums1[] = {
       1, 2, 3, 2, 2, 2, 5, 4, 2};
            int nums2[] = {
       4, 5, 1, 6, 2, 7, 3, 8};
    
            int result1[] = topK.GetLeastNumbers(nums1, 5);
            int result2[] = topK.GetLeastNumbers(nums2, 4);
            int result3[] = topK.GetLeastNumbers(nums2, nums2.length);
            int result4[] = topK.GetLeastNumbers(null, 1);
    
            CommonUtils.PrintArray(result1);
            CommonUtils.PrintArray(result2);
            CommonUtils.PrintArray(result3);
            CommonUtils.PrintArray(result4);
        }
        }