双指针快速排序：求解《最小的 k 个数》和《973.最接近原点的 K 个点》

双指针实现快速排序，求解《最小的k个数》和《973. 最接近原点的 K 个点》

思路

• 递归
  • 每次选中起始元素，作为pivot
  • 双指针从两端向中间移动
  • 升序时，左指针前都是<pivot，右指针后都是>pivot
  • 降序时，反之
  • 双指针停住，交换左右指针元素
  • 双指针相遇，交换起始和左指针元素
• 递归pivot左侧
• 递归pivot右侧

代码

传入数组

function quickSort(ar) {
  const d = (start, end) => {
    if (start >= end) return
    const pivot  = ar[start]
    let l = start, r = end
    while(l < r) {
        while(l < r && ar[r] >= pivot) r--
        while(l < r && ar[l] <= pivot) l++
        ;[ar[l], ar[r]] = [ar[r], ar[l]] // 分号不可省略
    }
    [ar[start], ar[l]] = [ar[l], ar[start]]
    d(start, l - 1)
    d(l + 1, end)
  }
  d(0, ar.length - 1)
  return ar
}

添加到数组的原型

Array.prototype.quickSort = function () {
  const d = (start, end) => {
      if (start >= end) return
      const pivot = this[start]
      let l = start, r = end
      while (l < r) {
        while (l < r && this[r] >= pivot) r--
        while (l < r && this[l] <= pivot) l++
        ;[this[l], this[r]] = [this[r], this[l]] // 分号不可省略
      }
      [this[start], this[l]] = [this[l], this[start]]
      d(start, l - 1)
      d(l + 1, end)
  }
  d(0, this.length - 1)
  return this
}

例题

剑指 Offer 40. 最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

答案

var getLeastNumbers = function(arr, k) {
  const quickSort = ar => {
    const d = (start, end) => {
      if (start >= end) return // 可省略
      const pivot = ar[start]
      let l = start, r = end
      while (l < r) {
        while (l < r && ar[r] >= pivot) r--
        while (l < r && ar[l] <= pivot) l++
        ;[ar[l], ar[r]] = [ar[r], ar[l]]
      }
      [ar[start], ar[l]] = [ar[l], ar[start]]
      if (l === k) return ar
      if (l > k) d(start, l - 1)
      else d(l + 1, end)
    }
    d(0, ar.length - 1)
    return ar
  }
  return quickSort(arr).slice(0, k)
};

最接近原点的 K 个点

给定一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点，并且是一个整数 k ，返回离原点 (0,0) 最近的 k 个点。 这里，平面上两点之间的距离是 欧几里德距离（ √(x1 - x2)2 + (y1 - y2)2 ）。 你可以按 任何顺序 返回答案。除了点坐标的顺序之外，答案 确保 是 唯一 的。

答案

var kClosest = function(points, k) {
  if (k >= points.length) return points
  const getEuclidianDistance = (x, y) => x ** 2 + y ** 2
  const quickSort = ar => {
    const d = (start, end) => {
      // if (start >= end) return ar
      const pivot = ar[start].euclidianDistance
      let l = start, r = end
      while (l < r) {
        while (l < r && ar[r].euclidianDistance >= pivot) r--
        while (l < r && ar[l].euclidianDistance <= pivot) l++
        ;[ar[l], ar[r]] = [ar[r], ar[l]]
      }
      [ar[start], ar[l]] = [ar[l], ar[start]]
      if (l === k) return ar
      if (l > k) d(start, l - 1)
      else d(l + 1, end)
    }
    d(0, ar.length - 1)
    return ar
  }
  for (const point of points) {
    point.euclidianDistance = getEuclidianDistance(point[0], point[1])
  }
  return quickSort(points).slice(0, k)
};