题解 | #最小的K个数#

• 思路1 冒泡排序思路 冒泡出k个最小的值即ok

import java.util.ArrayList;

public class Solution {   
    public ArrayList<integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<integer> res = new ArrayList<integer>();
        if(k>input.length) return res;
        for(int i = 0; i < k; ++i){
            int minIdx = i;
            for(int j = i+1;j < input.length;++j){
                if(input[minIdx]>input[j]){
                    minIdx = j;
                }
            }
            res.add(input[minIdx]);
            input[minIdx]  += input[i];;
            input[i] = input[minIdx] - input[i];
            input[minIdx] = input[minIdx] - input[i];
        }
        return res;
    }
}

• 思路2
  排序+取前k个数，这里主要是练习一下快排

import java.util.ArrayList;

public class Solution { 
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {

        ArrayList<Integer> res = new ArrayList<Integer>();
        if(k > input.length) return res;
        quickSort(input,0,input.length-1);

        for(int i =0; i < k; ++i){
            res.add(input[i]);
        }
        return res;
    }

    void quickSort(int [] input,int l, int r){
        if(l>=r) return;
        int i = l,j = r;
        int value = input[i];
        while(i < j){
            while(i<j && input[j] >= value){
                j--;
            }
            if(i < j){
                input[i] = input[j];
                i++;
            }
            while(i<j && input[i] < value){
                i++;
            }
            if(i<j){
                input[j] = input[i];
                j--;
            }
        }
        input[i] = value;
        quickSort(input,l,i-1);
        quickSort(input,i+1,r);
    }
}

• 思路3 快排变形：快排的核心思想是将数组中比当前数小的数移到左边，比当前数大的数移到右边，因此，每次快排后，判断当前数是否是数组中的第k个数，如果是，则可以知道k及k左侧的数是前k个数。取出返回即可。
  排序

  import java.util.ArrayList;
  public class Solution {  
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
  
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(k > input.length) return res;
        quickSort(input,0,input.length-1,k);
  
        for(int i =0; i < k; ++i){
            res.add(input[i]);
        }
        return res;
    }
  
    void quickSort(int [] input,int l, int r,int k){
        if(l>=r) return;
        int i = l,j = r;
        int value = input[i];
        while(i < j){
            while(i<j && input[j] >= value){
                j--;
            }
            if(i < j){
                input[i] = input[j];
                i++;
            }
            while(i<j && input[i] < value){
                i++;
            }
            if(i<j){
                input[j] = input[i];
                j--;
            }
        }
        input[i] = value;
        //核心代码在这里
        //如果当前值的索引即为k，则停止递归查找，直接返回
        //如果k在当前数的左侧，则对左侧子数组快排查找，右侧不用看了
        //如果在当前数的右侧，则对右侧子数组快排查找，左侧不用看了
        if( i == k) return;
        if(k <i){
            quickSort(input,l,i-1,k);
        }
        else{
            quickSort(input,i+1,r,k);
        }
    }
  }

• 思路4：堆排序
  见链接： 博客

import java.util.ArrayList;
public class Solution {   
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {

        ArrayList<Integer> res = new ArrayList<Integer>();
        if(k > input.length) return res;

        //1.建立小顶堆
        for(int idxNode = input.length/2-1; idxNode>=0;--idxNode){
            //对每个节点，调整其堆顺序
            AdjustNode(input, idxNode,input.length);
        }

        //2.按序出堆
        for(int idxOut = input.length-1; idxOut>=0;--idxOut,--k){
            if(k == 0) break;
            //将最小值出堆（调整到堆末尾、放入结果数组中）

            res.add(input[0]);
            int tmp = input[idxOut];
            input[idxOut] = input[0];
            input[0] = tmp;
            AdjustNode(input,0,idxOut);
        }

        return res;
    }

    int AdjustNode(int [] input, int idxNode, int idxResArea ){
        int iNodeValue = input[idxNode];
        while((idxNode*2+1) <idxResArea){
            //找出左右孩子中的较小值
            int min = idxNode*2+1;
            if((min+1) < idxResArea && input[min+1] < input[min]){
                min = min+1;
            }
            //如果较小值小于父节点，则父节点让位
            if(input[min] < iNodeValue){
                input[idxNode] = input[min];
                //竞争腾出来的子节点位置
                idxNode = min;
            }
            //否则父节点已经到位了
            else{
                break;
            }
        }
        input[idxNode] = iNodeValue;
        return 0;
    }
}

防吞格式

防吞格式
防吞格式
防吞格式
防吞格式
防吞格式
防吞格式
防吞格式
防吞格式