题解 | 最小的K个数

import java.util.*;


public class Solution {

    // 找出数组中不去重的最小的k个数
    // 思路：先排序，之后返回前k个数
  	// 本代码使用归并排序
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        // write code here
        ArrayList<Integer> list = new ArrayList<>();
        if(k == 0 || input.length == 0) return list;
        int n = input.length;
        mergeSort(0,n-1,input);
        int[] res = Arrays.copyOfRange(input,0,k);
        for(int i = 0;i<k;i++){
            list.add(res[i]);
        }
        return list;
    }

    public void mergeSort(int left, int right, int[] data){
        if(left >= right){
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(left,mid,data);
        mergeSort(mid + 1, right,data);

        merge(data,left,mid,right);
    }
    public void merge(int[] data,int left, int mid, int right){
        int[] temp = new int[right - left + 1];
        for(int i = left;i<=right;i++){
            temp[i - left] = data[i];
        }

        // 双指针合并
        int i = 0;
        int j = mid - left + 1;
        int k = left;
        while(i <= mid - left && j <= right - left){
            if(temp[i] <= temp[j]){
                data[k++] = temp[i++];
            }else{
                data[k++] = temp[j++];
            }
        }

        // 复制左子数组的剩余元素
        while(i <= mid - left){
            data[k++] = temp[i++];
        }
        while(j<=right - left){
            data[k++] = temp[j++];
        }
    }
}