剑指leetcode—最小K个数

题目描述：设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。 示例：

输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]

提示：
0 <= len(arr) <= 100000
0 <= k <= min(100000, len(arr))

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/smallest-k-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一：

暴力法

直接对数组排序，然后返回数组中的前k个数，很简单实现

方法二：

快速排序划分

根据题目意思可知，以任意顺序返回即可，所以我们需要找到在下标为k-1处的划分元素，然后直接返回k-1（包括自身）左边的所有元素

java实现：

class Solution {
    public int[] smallestK(int[] arr, int k) {
        if(k>=arr.length)
        return arr;
        int low=0;
        int high=arr.length-1;
        while(low<high)
        {
            int pos=partition(arr,low,high);
            if(pos==k-1)
            break;
            else if(pos<k-1)
            low=pos+1;
            else
            high=pos-1;
        }
        int [] ans=new int[k];
        return Arrays.copyOfRange(arr,0,k);
    }
   private int partition(int [] arr,int low,int high)
   {
       int pivot=arr[low];
       while(low<high)
       {
           while(low<high&&arr[high]>=pivot)
           high--;
           arr[low]=arr[high];
           while(low<high&&arr[low]<=pivot)
               low++;
               arr[high]=arr[low];
       }
       arr[low]=pivot;
       return low;
   }
}

方法三：

最小堆

System.arrayCopy的源代码声明 :
public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
代码解释:

Object src : 原数组
int srcPos : 从原数据的起始位置开始
Object dest : 目标数组 int
destPos : 目标数组的开始起始位置
int length : 要copy的原数组的长度

class Solution {
    public int[] smallestK(int[] arr, int k) {
    int len=arr.length;
    int [] lnums=new int[len+1];
    for(int i=len-1;i>=0;i--)
    lnums[i+1]=arr[i];
    minheapcreate(lnums,len);//建立小顶堆
    for(int i=1;i<=k;i++)
    {
        int t=lnums[1];
        lnums[1]=lnums[len-i+1];
        lnums[len-i+1]=t;
        minheapify(lnums,1,len-i);
    }
    return Arrays.copyOfRange(lnums,len+1-k,len+1);
   /*   也可以这样返回结果
   int [] res=new int[k];
    System.arraycopy(lnums,len+1-k,res,0,k);
    return res;
    }
    */
    void minheapcreate(int [] array, int  heapsize)  
 { 
      int i;  
      for(i = heapsize/2; i > 0; i--)  
      {  
          minheapify(array, i,heapsize);  
      }  
  }
    void minheapify(int [] nums,int k,int len)
{
    int i;
    nums[0]=nums[k];
    for(i=2*k;i<=len;i*=2)
    {
        if(i<len&&nums[i]>nums[i+1])i++;
        if(nums[0]<=nums[i])break;
        else
        {
            nums[k]=nums[i];
            k=i;
        }
    }
    nums[k]=nums[0];
}
}