题解 | #第k轻的牛牛#【Java】

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weights int整型一维数组 
     * @param k int整型 
     * @return int整型
     */
      public int findKthSmallest (int[] weights, int k) {
        int [] nums = new int [5000];
        for (int i = 0; i < weights.length; i++) {
            nums[weights[i]]++;
        }
        for (int i = 0; i < nums.length; i++) {
            while(nums[i]>0){
                nums[i]--;
                k--;
                if(k==0){
                    return i;
                }
            }
        }
        return 0;
    }
}

本题知识点分析:

1.数组遍历

2.计数排序

本题解题思路：

1.首先题目说明weight[i]在0到5000之间，这个数字很小，常量级

2.先统计某个重量的牛群数量个数

3.遍历nums数组，当nums[i]>0说明与牛群数量

4.nums[i]--,并且k--,当k==0说明是第K小的，因为i从0开始，如果找第K大的，从5000开始，倒序找就可以了

总结：类似计数排序，数学模拟，我看很多人题解用什么快速排序，冒泡排序，我寻思题解是O（n）要求啊，面试官要求O(n)你也这么搞？没意义啊，而且你直接调用库函数的sort更没意义了，做题复习下不好吗.....果然还是应试教育

本题使用编程语言: Java