20200919.md

Algorithm

剑指offer-最小的K个数

Description

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

Solution

import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] array, int k) {
        ArrayList<Integer> leastNumbers = new ArrayList<>();
        if (array == null || k <= 0 || k > array.length) {
            return leastNumbers;
        }
        //初始化为最大堆
        for (int i = k / 2 - 1; i >= 0; i--) {
            adjustHeap(array, i, k);
        }
        //从第k个元素开始分别与最大堆的最大值做比较，如果比最大值小，则替换并调整堆,最终堆里的就是最小的K个数
        for (int i = k; i < array.length; i++) {
            if (array[i] < array[0]) {
                int temp = array[0];
                array[0] = array[i];
                array[i] = temp;
                adjustHeap(array, 0, k);
            }
        }
        for (int i = 0; i < k; i++) {
            leastNumbers.add(array[i]);
        }
        return leastNumbers;
    }

    private void adjustHeap(int[] array, int parentIndex, int end){
        int temp = array[parentIndex];
        int childIndex = 2 * parentIndex + 1;
        while (childIndex < end) {
            if (childIndex + 1 < end && a) {
                childIndex++;
            }
            if (array[childIndex] < temp) {
                break;
            }
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * parentIndex + 1;
        }
        array[parentIndex] = temp;
    }
}

Discuss

根据堆排序的思想，先转换成堆然后再进行排序

Review

Tip

Share