通用方法：
快排/优先队列
多路归并：使用[哈希表]和优先队列找到K个最小的数即可！
二分：二分目标值统计小于等于该值的元素个数，正好为K个时返回其中最大的元素。

786. 第 K 个最小的素数分数

给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr 由 1 和若干 素数 组成，且其中所有整数互不相同。
对于每对满足 0 < i < j < arr.length 的 i 和 j ，可以得到分数 arr[i] / arr[j] 。
那么第 k 个最小的分数是多少呢? 以长度为 2 的整数数组返回你的答案, 这里 answer[0] == arr[i] 且 answer[1] == arr[j] 。
示例 1：
输入：arr = [1,2,3,5], k = 3 输出：[2,5] 解释：已构造好的分数,排序后如下所示: 1/5, 1/3, 2/5, 1/2, 3/5, 2/3 很明显第三个最小的分数是 2/5
示例 2：
输入：arr = [1,7], k = 1 输出：[1,7]

提示：

  • 2 <= arr.length <= 1000
  • 1 <= arr[i] <= 3 * 104
  • arr[0] == 1
  • arr[i] 是一个 素数 ，i > 0
  • arr 中的所有数字 互不相同 ，且按 严格递增 排序
  • 1 <= k <= arr.length * (arr.length - 1) / 2

思路：
方法一：多路归并
使用优先队列找到K个最小的数，返回第K个最小的数
方法二：二分
二分答案X，找到小于等于X的所有元素，恰为K个时返回其中最大的一个即可。

  1. // 多路归并
  2. class Solution {
  3.     public int[] kthSmallestPrimeFraction(int[] arr, int k) {
  4.         PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> (arr[o1[0]] * arr[o2[1]] - arr[o2[0]] * arr[o1[1]]));
  5.         for (int i = 1; i < arr.length; i++)
  6.             q.offer(new int[]{0, i});
  8.         int[] res = new int[2];
  9.         while (k-- > 0) {
  10.             // System.out.println(q);
  11.             int[] p = q.poll();
  12.             res[0] = arr[p[0]];
  13.             res[1] = arr[p[1]];
  14.             if (p[0] + 1 < p[1])
  15.                 q.offer(new int[]{p[0] + 1, p[1]});
  16.         }
  17.         return res;
  18.     }
  19. }
  1. // 二分
  2. class Solution {
  3.     public int[] kthSmallestPrimeFraction(int[] arr, int k) {
  4.         double l = 0, r = 1.0;
  5.         int x = 0, y = 1;
  6.         while (true) {
  7.             double mid = (l + r) / 2;
  8.             int cnt = 0;
  9.             x = 0;
  10.             y = 1;
  11.             for (int j = -1, i = 1; i < arr.length; i++) {
  12.                 while (1.0 * arr[j + 1] / arr[i] < mid) {
  13.                     j++;
  14.                     if (x * arr[i] < y * arr[j]) {
  15.                         x = arr[j];
  16.                         y = arr[i];
  17.                     }
  18.                 }
  19.                 cnt +=  j + 1;
  20.             }
  21.             if (cnt == k)
  22.                 return new int[]{x, y};
  23.             if (cnt < k)
  24.                 l = mid;
  25.             else
  26.                 r = mid;
  27.         }
  28.     }
  29. }

440. 字典序的第K小数字

给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字。

示例 1:
输入: n = 13, k = 2 输出: 10 解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
示例 2:
输入: n = 1, k = 1 输出: 1

提示:

  • 1 <= k <= n <= 109

思路：
数位统计问题
考虑前缀出现的次数，从前往后确定每一位

  1. class Solution {
  2.     public int findKthNumber(int n, int k) {
  3.         int prefix = 1;
  4.         while (k > 1) {
  5.             int cnt = find(prefix, n);
  6.             if (cnt >= k) {
  7.                 prefix *= 10;
  8.                 k--;
  9.             } else {
  10.                 prefix++;
  11.                 k -= cnt;
  12.             }
  13.         }
  14.         return prefix;
  15.     }
  17.     int find(int prefix, int n) {
  18.         String s = String.valueOf(n), t = String.valueOf(prefix);
  19.         long p = 1;
  20.         int len = s.length() - t.length();
  21.         long res = 0;
  22.         for (int i = 0; i < len; i++) {
  23.             res += p;
  24.             p *= 10;
  25.         }
  26.         s = s.substring(0, t.length());
  27.         if (s.compareTo(t) > 0) {
  28.             res += p;
  29.         } else if (s.compareTo(t) == 0) {
  30.             res += n - prefix * p + 1;
  31.         }
  32.         return (int)(res);
  33.     }
  34. }

215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:
输入: [3,2,1,5,6,4] 和 k = 2 输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4

提示：

  • 1 <= k <= nums.length <= 104
  • -104 <= nums[i] <= 104

思路：
优先队列/快速排序

  1. // 优先队列
  2. class Solution {
  3.     public int findKthLargest(int[] nums, int k) {
  4.         PriorityQueue<Integer> q = new PriorityQueue<>();
  5.         for (int x : nums) {
  6.             q.offer(x);
  7.             if (q.size() > k)
  8.                 q.poll();
  9.         }
  10.         return q.poll();
  11.     }
  12. }
  14. // 快速排序
  15. class Solution {
  16.     public int findKthLargest(int[] nums, int k) {
  17.         int n = nums.length;
  18.         return quickSort(nums, 0, n - 1, k - 1);
  19.     }
  21.     int quickSort(int[] nums, int l, int r, int k) {
  22.         if (l == r)
  23.             return nums[l];
  25.         int x = nums[l + r >> 1];
  26.         int i = l - 1, j = r + 1;
  27.         while (i < j) {
  28.             while (nums[++i] > x);
  29.             while (nums[--j] < x);
  30.             if (i < j) {
  31.                 int t = nums[i];
  32.                 nums[i] = nums[j];
  33.                 nums[j] = t;
  34.             }
  35.         }
  37.         if (j >= k)
  38.             return quickSort(nums, l, j, k);
  39.         else
  40.             return quickSort(nums, j + 1, r, k);
  41.     }
  42. }

面试题 17.14. 最小K个数

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
示例：
输入： arr = [1,3,5,7,2,4,6,8], k = 4 输出： [1,2,3,4]
提示：

  • 0 <= len(arr) <= 100000
  • 0 <= k <= min(100000, len(arr))

思路：
快排/优先队列

  1. // 优先队列
  2. class Solution {
  3.     public int[] smallestK(int[] arr, int k) {
  4.         PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2) -> o2.compareTo(o1));
  5.         for (int x : arr) {
  6.             q.offer(x);
  7.             if (q.size() > k)
  8.                 q.poll();
  9.         }
  10.         int[] res = new int[k];
  11.         for (int i = k - 1; i >= 0; i--)
  12.             res[i] = q.poll();
  13.         return res;
  14.     }
  15. }
  17. // 快排
  18. class Solution {
  19.     public int[] smallestK(int[] arr, int k) {
  20.         int n = arr.length;
  21.         quickSort(arr, 0, n - 1, k - 1);
  22.         int[] res = new int[k];
  23.         for (int i = 0; i < k; i++)
  24.             res[i] = arr[i];
  25.         return res;
  26.     }
  28.     void quickSort(int[] q, int l, int r, int k) {
  29.         if (l >= r)
  30.             return;
  32.         int x = q[l + r >> 1], i = l - 1, j = r + 1;
  33.         while (i < j) {
  34.             while (q[++i] < x);
  35.             while (q[--j] > x);
  36.             if (i < j) {
  37.                 q[i] ^= q[j];
  38.                 q[j] ^= q[i];
  39.                 q[i] ^= q[j];
  40.             }
  41.         }
  43.         if (k <= j)
  44.             quickSort(q, l, j, k);
  45.         else
  46.             quickSort(q, j + 1, r, k);
  47.     }
  48. }