美文网首页剑指offer
剑指offer-面试题40:最小的K个数

剑指offer-面试题40:最小的K个数

作者: 依然慢节奏 | 来源:发表于2020-05-14 18:10 被阅读0次

    题目描述

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

    思路分析

    两种思路可以实现,第一种是利用插入排序来实现,首先维持一个长度为K的有序序列,然后将剩下的数字插入到有序序列中去,直到最后一个元素,插入排序结束后就前面K个元素就是最小的K个数;

    第二种是利用快速排序来实现,需要改动一下,判断每次返回的partition位置是否等于K,根据返回的位置下标进行左右递归分治,直到最终返回的partition位置等于K时,前面K个元素就是题目要求的最小K个数;

    代码实现

     import java.util.ArrayList;
    
    public class Solution {
          /**
         * 链接:https://www.nowcoder.com/questionTerminal/6a296eb82cf844ca8539b57c23e6e9bf?answerType=1&f=discussion
         * 来源:牛客网
         * 维持一个K长度的最小值集合,然后利用插入排序的思想进行对前K个元素的不断更新。
         */
        public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
    
            ArrayList<Integer> result = new ArrayList<Integer>();
            if (k <= 0 || k > input.length)
                return result;
            //初次排序,完成k个元素的排序
            for (int i = 1; i < k; i++) {
                int j = i - 1;
                int unFindElement = input[i];
                while (j >= 0 && input[j] > unFindElement) {
                    input[j + 1] = input[j];
                    j--;
                }
    
                input[j + 1] = unFindElement;
            }
            //遍历后面的元素 进行k个元素的更新和替换
            for (int i = k; i < input.length; i++) {
                if (input[i] < input[k - 1]) {
                    int newK = input[i];
                    int j = k - 1;
                    while (j >= 0 && input[j] > newK) {
                        input[j + 1] = input[j];
                        j--;
                    }
                    input[j + 1] = newK;
                }
            }
            //把前k个元素返回
            for (int i = 0; i < k; i++)
                result.add(input[i]);
            return result;
        }
    
        /**
         * 链接:https://www.nowcoder.com/questionTerminal/6a296eb82cf844ca8539b57c23e6e9bf?answerType=1&f=discussion
         * 来源:牛客网
         * <p>
         * 快排的partition函数会将原序列分为左右两个子序列,左边序列都小于pivot,右边序列都大于或等于pivot,
         * 当pivot为数组的第k个元素时,数组中pivot及其之前的元素都小于右边序列,即为n个整数中最小的k个数。
         */
        public ArrayList<Integer> GetLeastNumbers_SolutionV2(int[] input, int k) {
            if (input == null || input.length == 0 || input.length < k || k == 0) {
                return new ArrayList<>();
            }
            // 在数组中寻找位置为k - 1的pivot
            int start = 0, end = input.length - 1;
            int index = partition(input, start, end);
            while (index != k - 1) {
                if (index < k - 1) {
                    start = index + 1;
                } else {
                    end = index - 1;
                }
                index = partition(input, start, end);
            }
    
            // 收集这k个数
            ArrayList<Integer> res = new ArrayList<>();
            for (int i = 0; i <= index; i++) {
                res.add(input[i]);
            }
            return res;
        }
    
        // divide target range array to smaller hi value part and other part.
        private int partition(int[] arr, int start, int end) {
            int pivot = arr[end];
            int prePtr = start - 1;
            while (start < end) {
                if (arr[start] < pivot) {
                    swap(arr, start++, ++prePtr);
                } else {
                    start++;
                }
            }
            swap(arr, end, ++prePtr);
            return prePtr;
        }
    
    
        private void swap(int[] arr, int a, int b) {
            int temp = arr[b];
            arr[b] = arr[a];
            arr[a] = temp;
        }
    
        public static void main(String[] args) {
            int[] array = {4, 5, 1, 6, 2, 7, 3, 8};
            Q40_MinimumNumberOfK q40MinimumNumberOfK = new Q40_MinimumNumberOfK();
            //        ArrayList<Integer> arrayList = solution23.GetLeastNumbers_Solution(array, 4);
            ArrayList<Integer> arrayList = q40MinimumNumberOfK.GetLeastNumbers_SolutionV2(array, 4);
            System.out.println(arrayList);
            System.out.println(Arrays.toString(array));
        }
    }
    

    欢迎关注南阁公众号

    南阁子也

    相关文章

      网友评论

        本文标题:剑指offer-面试题40:最小的K个数

        本文链接:https://www.haomeiwen.com/subject/pxlxohtx.html