973. 最接近原点的 K 个点

发表于 | 分类于
拿到通用的大根堆之后写题简单很多了

用时：15min

常规堆排序没什么好说的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class Heap {
    constructor(list, compare = (a, b) => a - b) {
      this.left = index => 2 * index + 1
      this.right = index => 2 * index + 2
      this.parent = index => Math.floor((index - 1) / 2)
      this.heapify = (index = 0) => {
        const { list } = this
        const leftIndex = this.left(index)
        const rightIndex = this.right(index)
        let maxIndex = index
        if (list[leftIndex] !== undefined
          && this.compare(list[maxIndex], list[leftIndex]) > 0) {
          maxIndex = leftIndex
        }
        if (list[rightIndex] !== undefined
          && this.compare(list[maxIndex], list[rightIndex]) > 0) {
          maxIndex = rightIndex
        }
        if (index !== maxIndex) {
          const temp = list[index]
          list[index] = list[maxIndex]
          list[maxIndex] = temp
          this.heapify(maxIndex)
        }
      }
      this.buildHeap = () => {
        for (let i = Math.floor(this.list.length / 2); i >= 0; i--) {
          this.heapify(i)
        }
        return this.list
      }
      this.extract = () => {
        const temp = this.list[0]
        this.list[0] = this.list[this.list.length - 1]
        this.list[this.list.length - 1] = temp
        const result = this.list.pop()
        this.heapify(0)
        return result
      }
      this.top = () => {
          return this.list[0]
      }
      this.insert = (item) => {
        const { list } = this
        list.push(item)
        let index = list.length - 1
        let parentIndex = this.parent(index)
        while (list[parentIndex] !== undefined && this.compare(list[parentIndex], list[index]) > 0) {
          const temp = list[index]
          list[index] = list[parentIndex]
          list[parentIndex] = temp
          index = parentIndex
          parentIndex = this.parent(index)
        }
      }
      this.list = list
      this.compare = compare
      this.buildHeap()
    }
  }

var kClosest = function(points, k) {
    // 要找到最近的点，应该用最大堆存储 k 个最小的
    var compare = function (a,b) {
      var A = a[0] * a[0] + a[1] * a[1]
      var B = b[1] * b[1] + b[0] * b[0]
      return B - A
    }
    var heap = new Heap([],(a,b) => {
      return  compare(a,b)
    })
    for(let i = 0 ; i < points.length ; i ++) {
      if (i < k) {
        heap.insert(points[i])
      } else {
        var top = heap.top()
        // top   比  当前值大， 出top
        if(compare(points[i],top) > 0) {
          heap.extract()
          heap.insert(points[i])
        }
        
      }
    }
    return heap.list
};