Sword to Offer-40 最小的 K 个数 ❀

29 Apr 2020 in Algorithm

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

解题思路：

冒泡排序，外循环设为k次即可得到最小的k个值，相邻的两个值比较，将最小的值往右冒泡至无序部分的最后一个位置，每次外循环将冒泡上去的那个数添加到用于返回的链表中。

问题图解：

AC代码：

// Find the k Minimum Numbers in Array （Bubble Sort）

import java.util.ArrayList;

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

补充说明：

• 这里是牛客编码链接