关于java:offer-40-最小的k个数-还没写完

最小的 k 个数

题解

最小的 k 个数
就是求最小的几个数，把数组元素从小到大排列，而后输入后面的 k 个数就能够了，而后把这几个数赋给新的数组再返回就行

堆

PriorityQueue 是基于优先堆的一个无界队列，这个优先队列中的元素能够默认天然排序或者通过提供的 Comparator（比拟器）在队列实例化的时排序。要求应用 Java Comparable 和 Comparator 接口给对象排序，并且在排序时会依照优先级解决其中的元素。
(i1, i2) -> Integer.compare(i2, i1))
由从小到大排序变为从大到小排序
堆

疾速排序

public int[] getLeastNumbers(int[] arr, int k) {if (k == 0) {return new int[0];
    } else if (arr.length <= k) {return arr;}
    
    // 原地一直划分数组
    partitionArray(arr, 0, arr.length - 1, k);
    
    // 数组的前 k 个数此时就是最小的 k 个数，将其存入后果
    int[] res = new int[k];
    for (int i = 0; i < k; i++) {res[i] = arr[i];
    }
    return res;
}

void partitionArray(int[] arr, int lo, int hi, int k) {
    // 做一次 partition 操作
    int m = partition(arr, lo, hi);
    // 此时数组前 m 个数，就是最小的 m 个数
    if (k == m) {// 正好找到最小的 k(m) 个数
        return;
    } else if (k < m) {
        // 最小的 k 个数肯定在前 m 个数中，递归划分
        partitionArray(arr, lo, m-1, k);
    } else {
        // 在右侧数组中寻找最小的 k-m 个数
        partitionArray(arr, m+1, hi, k);
    }
}

// partition 函数和疾速排序中雷同，具体可参考疾速排序相干的材料
// 代码参考 Sedgewick 的《算法 4》int partition(int[] a, int lo, int hi) {
    int i = lo;
    int j = hi + 1;
    int v = a[lo];
    while (true) {while (a[++i] < v) {if (i == hi) {break;}
        }
        while (a[--j] > v) {if (j == lo) {break;}
        }

        if (i >= j) {break;}
        swap(a, i, j);
    }
    swap(a, lo, j);

    // a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
    return j;
}

void swap(int[] a, int i, int j) {int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}