【剑指offer】-最小K个数-28/67

今天药忘吃喽~ 2023-02-12 13:28 54阅读 0赞

# 一、题目描述 #

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

# 二、题目分析 #

1.  典型的排序题目，直接使用-[快速排序][Link 1]
2.  注意一下，input数组的空值和input.length的值与K值的比较

# 三、题目代码 #

package offer;
    
    import java.util.ArrayList;
    
    /*
     * 最小K个数
     */
    public class Test28 {
        
    	static ArrayList<Integer> list = new ArrayList<Integer>();
    
    	public static void main(String[] args) {
        
    		Test28 test28 = new Test28();
    		int[] input = new int[] {
         4, 5, 1, 6, 2, 7, 3, 8 };
    		list = test28.GetLeastNumbers_Solution(input, 4);
    		System.out.println(list);
    	}
    
    	public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        
    		if (input.length == 0 || input.length < k) {
        
    			return list;
    		}
    		sort(input, 0, input.length - 1);
    		for (int i = 0; i < k; i++) {
        
    			list.add(input[i]);
    		}
    		return list;
    	}
    
    	void sort(int[] input, int start, int end) {
        
    		if (start > end) {
        
    			return;
    		}
    		int i = start;
    		int j = end;
    		int key = input[i];
    		while (i < j) {
        
    			while (i < j && input[j] >= key) {
        
    				j--;
    			}
    			input[i] = input[j];
    			while (i < j && input[i] <= key) {
        
    				i++;
    			}
    			input[j] = input[i];
    		}
    		input[i] = key;
    		sort(input, start, i - 1);
    		sort(input, i + 1, end);
    	}
    
    }

[Link 1]: https://blog.csdn.net/qq_40915439/article/details/105888342

发表评论取消回复

表情：

评论列表（有 0 条评论，54人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指offer - 最小的K个数

class Solution { public: vector<int> GetLeastNumbers_Solution(vector<int

墨蓝/ 2022年09月25日 01:28/ 0 赞/ 178 阅读

相关剑指Offer 最小的K个数

题目描述: 输入n个整数，找出其中最小的k个数思路: 首先想到的是对数组进行按从小到大排序然后再选出最小的前K个数。排序算法里选择排序是每次排序都可以确定数组在最后排好

骑猪看日落/ 2022年06月10日 12:14/ 0 赞/ 293 阅读

相关剑指offer 最小的k个数

1.题目描述输入n个数字，找出其中最小的k个数。注：有的还会要求保持原有的顺序输出 2.分析两种思路： 1）利用快排的思想，找到第k大的分界点。左边的

男娘i/ 2022年06月08日 09:38/ 0 赞/ 245 阅读

相关剑指Offer:最小的k个数

题目：输入N个整数，找出其中最小的k个数。例如，输入4,5,1,6,2,7,3,8. 最小的4个数字是1,2,3,4. 思路：就是把那个容器只能存k个数，当容器未满时，直

骑猪看日落/ 2022年04月25日 03:08/ 0 赞/ 258 阅读

相关剑指offer:最小的k个数

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

以你之姓@/ 2022年04月10日 08:58/ 0 赞/ 293 阅读

相关剑指offer:最小的k个数

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

电玩女神/ 2022年02月26日 19:48/ 0 赞/ 273 阅读

相关剑指Offer-最小的K个数

题目描述输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。解题思路—快排：时间复杂度O(nl

Dear 丶/ 2022年02月21日 16:54/ 0 赞/ 339 阅读

相关 [剑指offer]最小的K个数

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。最大堆时间复杂度O（nlogk）

ゞ浴缸里的玫瑰/ 2021年12月19日 22:29/ 0 赞/ 322 阅读

相关最小k个数-剑指offer-Java

题目描述输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。解题思路：采用堆排序 1）将前k

古城微笑少年丶/ 2021年12月13日 04:44/ 0 赞/ 295 阅读

相关剑指offer：最小的K个数

试题：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。代码：使用有序结构存储这k个数就可以

旧城等待，/ 2021年06月24日 16:09/ 0 赞/ 442 阅读