题解 | #牛群中的第 k 小牛#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @param k int整型
     * @return int整型
     */
    public int findKthSmallest (int[] nums, int k) {
        // 计数排序 元素范围是-10000 - 10000 转化成 0 - 20000
        int [] temp = new int[20001];
	  // 将负数转化为正数索引存放
        for (int i = 0; i < nums.length; i++) {
            temp[nums[i]+10000]++;
        }
        for (int i = 0; i < temp.length; i++) {
		// 如果这个位置上有数值，那么数值的次数代码,i出现了几次
            if(temp[i]!=0){
			  // 临时记录出现次数
                int number = temp[i];
			  // 循环其实目的就是找出第k小的数字，因为i=0开始从前遍历，找的就是最小的
                while(number>0){
                    k--;
                    number--;
				  // 如果k==0表明找到了，返回i-10000即可，因为由于有负数，上面加了10000
                    if(k==0){
                        return i-10000;
                    }
                }
            }
        }
       return -1;
    }
  /**
  方法二:快速排序
  */
	  public int findKthSmallest(int[] nums, int k) {
		return quickSelect(nums, 0, nums.length - 1, k);
	}

	private int quickSelect(int[] nums, int left, int right, int k) {
		if (left == right) {
			return nums[left];
		}

		int pivotIndex = partition(nums, left, right);

		if (k == pivotIndex + 1) {
			return nums[pivotIndex];
		} else if (k < pivotIndex + 1) {
			return quickSelect(nums, left, pivotIndex - 1, k);
		} else {
			return quickSelect(nums, pivotIndex + 1, right, k);
		}
	}

	private int partition(int[] nums, int left, int right) {
		int pivot = nums[left];
		int i = left + 1; // 左侧指针
		int j = right; // 右侧指针

		while (i <= j) {
			if (nums[i] <= pivot) {
				i++;
			} else if (nums[j] >= pivot) {
				j--;
			} else {
				swap(nums, i, j);
				i++;
				j--;
			}
		}

		swap(nums, left, j); // 将pivot放置到正确的位置

		return j;
	}

	private void swap(int[] nums, int i, int j) {
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}
}

本题知识点分析：

1.计数排序

2.快速排序

3.数学模拟

4.数组遍历

本题解题思路分析：

1.将负数转化为正数索引存放

2.如果这个位置上有数值，那么数值的次数代码,i出现了几次

3.循环其实目的就是找出第k小的数字，因为i=0开始从前遍历，找的就是最小的

4.如果k==0表明找到了，返回i-10000即可，因为由于有负数，上面加了10000

本题也可以用快速排序做，但要自己手写，因为要做剪枝优化，时间复杂度才可以到O(n)

本题使用编程语言: Java

如果你觉得本题对你有帮助的话，可以点个赞支持一下，感谢~