75. 颜色分类

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {void} Do not return anything, modify nums in-place instead.
  4.  */
  5. var sortColors = function(nums) {
  6.   // [0, p1) = 0
  7.   // [p1, p2) = 1
  8.   // [p2, len-1] = 2
  9.   let p1 = -1;
  10.   let p2 = nums.length;
  11.   let i = 0;
  12.   const swap = (a, b) => [nums[a], nums[b]] = [nums[b], nums[a]];
  14.   while ( i < p2) {
  15.     if (nums[i] === 0) {
  16.       ++p1;
  17.       swap(i, p1);
  18.       i++;
  19.     } else if (nums[i] === 1) {
  20.       i++;
  21.     } else if (nums[i] === 2) {
  22.       --p2;
  23.       swap(i, p2);
  24.     }
  25.   }
  26. };

剑指 Offer II 076. 数组中的第 k 大的数字

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} k
  4.  * @return {number}
  5.  */
  6. var findKthLargest = function(nums, k) {
  7.   const swap = (l, r) => [nums[l], nums[r]] = [nums[r], nums[l]];
  9.   const comparator = (a, b) => {
  10.     return a > b;
  11.   };
  13.   const partition = (l, r, k) => {
  14.     // [l, i) < x
  15.     // i = x
  16.     // (i, r) > x
  17.     let x = nums[r-1], i = l, j = l;
  18.     while (j < r-1) {
  19.       if (comparator(nums[j], x)) {
  20.         swap(i, j);
  21.         i++;
  22.       }
  23.       j++;
  24.     }
  25.     swap(i, r-1);
  26.     return i;
  27.   };
  29.   const getK = (left, right, k) => {
  30.     while (true) {
  31.       let nextLeft = partition(left, right, k);
  32.       let len = nextLeft - left + 1;
  33.       if (k === len) {
  34.         return nums[nextLeft];
  35.       } else if (k < len) {
  36.         right = nextLeft;
  37.       } else if (k > len) {
  38.         left = nextLeft + 1;
  39.         k -= len;
  40.       }
  41.     }
  42.   }
  43.   return getK(0, nums.length, k);
  44. };

719. 找出第 k 小的距离对

难度困难189收藏分享切换为英文接收动态反馈
给定一个整数数组，返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。
示例 1:
输入：
nums = [1,3,1]
k = 1
输出：0
解释：
所有数对如下：
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
因此第 1 个最小距离的数对是 (1,1)，它们之间的距离为 0。

提示:

  1. 2 <= len(nums) <= 10000.
  2. 0 <= nums[i] < 1000000.

  3. 1 <= k <= len(nums) * (len(nums) - 1) / 2.

    /**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var smallestDistancePair = function(nums, k) {
nums.sort((a, b) => a-b);
let left = 0, right = nums[nums.length - 1] - nums[0];
while (left < right) {
 let mid = (left + right) >>> 1;
 // 满足单调性后，找距离不高于mid的距离对数目。
 let count = 0, i = 0;
 for (let j = 0; j < nums.length; j++) {
   while (nums[j] - nums[i] > mid) {
     i++;
   }
   count += j - i;
 }

 if (count < k) {
   left = mid + 1;
 } else {
   right = mid;
 }
}
return left;
};