剑指 Offer 40. 最小的k个数

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

示例 1：

输入：arr = [3,2,1], k = 2

输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1

输出：[0]

限制：

0 <= k <= arr.length <= 10000

0 <= arr[i] <= 10000

做题思路：其实做这道题，还是有点套模板的嫌疑，尤其是可以直接套快排的模板，先看答案之前，可以先学习一下左神的快排代码。

public class Code_04_QuickSort {

    public static void quickSort(int[] arr) {

        if (arr == null || arr.length < 2) {

            return;

        }

        quickSort(arr, 0, arr.length - 1);

    }

    public static void quickSort(int[] arr, int l, int r) {

        if (l < r) {

            //swap(arr, l + (int) (Math.random() * (r - l + 1)), r);

            int[] p = partition(arr, l, r);

            quickSort(arr, l, p[0] - 1);

            quickSort(arr, p[1] + 1, r);

        }

    }

	//设置了less,more作为左右两个边界，然后让l来与more相互比较，然后再进行交换数据，并移动l或者more的位置

    public static int[] partition(int[] arr, int l, int r) {

        int less = l - 1;

        int more = r;

        while (l < more) {

            if (arr[l] < arr[r]) {

                swap(arr, ++less, l++);

            } else if (arr[l] > arr[r]) {

                swap(arr, --more, l);

            } else {

                l++;

            }

        }

        swap(arr, more, r);

        return new int[] { less + 1, more };

    }

	//交换数组的数据

    public static void swap(int[] arr, int i, int j) {

        int tmp = arr[i];

        arr[i] = arr[j];

        arr[j] = tmp;

    }

}

一、哨兵操作

class Solution1 {

        /*

        这是执行的哨兵的操作，设置一个基数，大于这个基数移动到右边，小于这个相反即可

         */

        public int[] getLeastNumbers(int[] arr, int k) {

            quickSort(arr, 0, arr.length - 1);

            return Arrays.copyOf(arr, k);

        }

        private void quickSort(int[] arr, int l, int r) {

            //当数组长度为1时终止

            if (l >= r) return;

            int i = l, j = r;

            //这里是把arr[l]当做基数，然后和arr[i]和arr[j]做对比，和快排或者荷兰国旗问题有点像，大于或者小于就--或者++

            while (i < j) {

                while (i < j && arr[j] >= arr[l]) j--;

                while (i < j && arr[i] <= arr[l]) i++;

                swap(arr, i, j);

            }

            swap(arr, i, l);

            //这是递归左(右)执行左右两边的划分

            quickSort(arr, l, i - 1);

            quickSort(arr, i + 1, r);

        }

        private void swap(int[] arr, int i, int j){

            int tmp = arr[i];

            arr[i] = arr[j];

            arr[j] = tmp;

        }

    }

二、快排

class Solution2 {

        /*

        这是一个快排的操作思路

         */

        public int[] getLeastNumbers(int[] arr, int k) {

            if (k >= arr.length) return arr;

            return quickSort(arr, k, 0, arr.length - 1);

        }

        private int[] quickSort(int[] arr, int k, int l, int r) {

            int i = l, j = r;

            while (i < j) {

                while (i < j && arr[j] >= arr[l]) j--;

                while (i < j && arr[i] <= arr[l]) i++;

                swap(arr, i, j);

            }

            swap(arr, i, l);

            /*

            这里

            i > k 则递归 左边的快排(左边的数组)

            i < k 则递归 右边的快排(右边的数组)

             */

            if (i > k) return quickSort(arr, k, l, i - 1);

            if (i < k) return quickSort(arr, k, i + 1, r);

            return Arrays.copyOf(arr, k);

        }

        private void swap(int[] arr, int i, int j){

            int tmp = arr[i];

            arr[i] = arr[j];

            arr[j] = tmp;

        }

    }

巴特西

剑指 Offer 40. 最小的k个数

剑指 Offer 40. 最小的k个数

最新文章

热门文章