973. K Closest Points to Origin

最接近原点的 k 个点

使用原生的sort方法

• Runtime: 176 ms, faster than 83.83%
• Memory Usage: 48.1 MB, less than 84.81%
• 时间复杂度O(n)，空间复杂度O(n)

/**
 * @param {number[][]} points
 * @param {number} k
 * @return {number[][]}
 */
var kClosest = function(points, k) {
  points.sort((a, b) => (a[0] ** 2 + a[1] ** 2) - (b[0] ** 2 + b[1] ** 2));
  return points.slice(0, k);
};

使用快排的sort方法

• Runtime: 184 ms, faster than 74.49%
• Memory Usage: 49.1 MB, less than 75.40%

/**
 * @param {number[][]} points
 * @param {number} k
 * @return {number[][]}
 */

var getDistance = (point) => {
  const [x, y] = point;
  return x ** 2 + y ** 2;
}

var kClosest = function(points, k) {
  const pivotIdx = Math.floor(Math.random() * points.length);
  const pivot = points[pivotIdx];
  const pivotDistance = getDistance(pivot);
  console.log(pivotDistance)
  const left = [];
  const right = [];
  points.forEach(p => {
    const distance = getDistance(p);
    if (distance < pivotDistance) {
      left.push(p);
    } else if (distance > pivotDistance){
      right.push(p);
    } else {
      if (left.length < k) {
        left.push(p);
      }
    }
  });
  
  if (left.length === k) {
    return left;
  } else if (left.length < k) {
    return kClosest(right, k - left.length).concat(left);
  }
  
  return kClosest(left, k);
}