题解 | #最小的K个数#

最小的K个数

https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param input int整型一维数组
     * @param k int整型
     * @return int整型ArrayList
     */
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        // write code here
        ArrayList<Integer> list = new ArrayList<>(k);
        if (input.length < k) {
            return list;
        }
        quickSort(input, 0, input.length - 1);
        for (int i = 0; i < k; i++) {
            list.add(input[i]);
        }


        return list;
    }



    public static void quickSort(int[] arr, int low, int high) {
        //log.info("arr: {},low:{},high:{}", arr, low, high);
        if (low < high) {
            // 找到划分点
            int pivotIndex = index(arr, low, high);
            //log.info("pivotIndex: {},arr:{}", pivotIndex, arr);

            // 递归地对左右两部分进行快速排序
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }



    private static int index(int[] array, int low, int high) {
        int idx = array[high];
        int i = (low - 1);
        for (int j = low ; j < high ; j++) {
            if (idx >= array[j]) {
                i++;
                // 移动数据,小于基准值的放在最左面
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        // 本次移动之后,将基准值放入左面 i 之后
        int temp = array[i + 1] ;
        array[i + 1] = array[high];
        array[high] = temp;
        return i + 1;
    }

}


排序后截取数据

全部评论

相关推荐

AAA专业长城贴瓷砖刘大爷:这样的简历我会直接丢进垃圾桶,花里胡哨的
点赞 评论 收藏
分享
05-12 11:09
已编辑
门头沟学院 后端
已注销:没必要放这么多专业技能的描述。这些应该是默认已会的,写这么多行感觉在凑内容。项目这块感觉再包装包装吧,换个名字,虽然大家的项目基本都是网上套壳的,但是你这也太明显了。放一个业务项目,再放一个技术项目。技术项目,例如中间件的一些扩展和尝试。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务