剑指offer_【29】最小的K个数

1.题目描述

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

2.解题思路

排序问题，本次使用快排，快排思想即：

“挖坑填数+分治法”，首先令i =L; j = R; 将a[i]挖出形成第一个坑，称a[i]为基准数。然后j–由后向前找比基准数小的数，找到后挖出此数填入前一个坑a[i]中，再i++由前向后找比基准数大的数，找到后也挖出此数填到前一个坑a[j]中。重复进行这种“挖坑填数”直到i==j。再将基准数填入a[i]中，这样i之前的数都比基准数小，i之后的数都比基准数大。

3.代码

import java.util.*;
public class Solution {
   public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        if(input.length<k)
            return res;
        quicksort(input, 0, input.length - 1);
        for (int i = 0; i < k; i++) {
            res.add(input[i]);
        }
        return res;
    }
    public void quicksort(int arr[], int low, int high)
    {
        if(low < high)
        {
            int position = partition(arr, low, high);
            quicksort(arr, low, position - 1);
            quicksort(arr, position + 1, high);
        }

    }
        public  int partition(int arr[], int low, int high) {
            //设置基准值
            int key = arr[low];
            while(low < high){
                //从右到左，直到找到一个小于key的值
                while(low < high && arr[high] >= key) --high;
                //将该值填入前的坑
                arr[low] = arr[high];
                //从左到右，直到找到一个大于key的值
                while(low < high && arr[low] <= key) ++low;
                //将该值填入前一个坑
                arr[high] = arr[low];
            }
            //将基准值填入最后一个坑
            arr[low] = key;
            //最后一个坑划分了左边小于该值，右边大于该值
            return low;
        }

}