15 -- k points closest to the origin

subject

Github link
Closest to the origin K A little bit

Given an array points , among points[i] = [xi, yi] Express X-Y A point on the plane , And is an integer k , Return from origin (0,0) Current k A little bit .

here , The distance between two points on the plane is Euclid distance （ √(x1 - x2)2 + (y1 - y2)2 ）.

You can press In any order Return to the answer . In addition to the order of point coordinates , answer Make sure yes only Of .

• Ideas

1. Of course you can sort , Find the front again K Number
2. But this problem mainly focuses on building piles , This is the classic topK problem , at the idea of topK problem , You have to think about building a heap
3. So here comes the question , Build a small top pile or a large top pile ？
4. First remember the pithy formula ：

topK Small , Big pile top ;topK Big , Small cap pile

5. Why is that so ？
   （1） Because of the demand topK When I was a child , Build a large top pile , The top element of the heap is this topK The biggest element in the small , This makes it easy for the following elements to compare ;

   for instance ,[2,4,6,5,1] in , Seek before top3 Small value
   Build a large top pile , The length of the heap is 3
   Easy to come by ： The top of the pile is 6, Zuo Wei 2, Right for 4,
   The current heap is :[6,2,4]
   When new elements 5 Come in and build a pile , When comparing
   Take out the top element first 6 To compare , Find out 6 Than 5 Big ,
   （a） Then add to the array obtain : [6,2,4,5]
   （b） Then swap the first and last elements of the array , obtain : [5,2,4,6]
   （c） Delete the last element , obtain : [5,2,4]
   This is the latest heap , And so on
   （d） When 1 To build the reactor , obtain : [1,2,4]
   To this end , obtain top3 The small element is [1,2,4]

(2) seek topK Big , Build a small top pile , The principle is similar to the above .

• answer
• The code of this problem ：

class facebook03 {
    //  Find the least distance topK, Build a large top pile 
    //  The top element of the heap , yes topK The last , in other words , Value after , Compare , Just compare it to the top element 
    //  That's why , seek topK Small , Build a large top pile 
    //  On the other hand , If o topK Big , Just build a small top pile 
    //  Sum up the memory formula : topK Big , Small cap pile ;topK Small , Big pile top 
    
    var lock = NSLock()
    func kClosest(_ points: [[Int]], _ k: Int) -> [[Int]] {
        let heap = MyHeap(k)
        
        for i in 0..<points.count {
            let curPoint = points[i]
            lock.lock()
            let val = helper(curPoint) //[[6,10],[-3,3],[-2,5],[0,2]]
            print(i,"--",val)
            heap.createHeap([i: val])
            lock.unlock()
        }
        
        var res = [[Int]]()
        
        for i in 0..<k {
            let ele = heap.heapArr[i]
            let index = ele.first!.key
            res.append(points[index])
        }
        
        return res
    }
    
    func helper(_ p:[Int]) -> Int {
        return p[0] * p[0] + p[1] * p[1]
    }
}

class MyHeap {
    var heapArr = [[Int: Int]]()
    var topK: Int!
    init(_ top: Int) {
        topK = top
    }
    

    func createHeap(_ dict: [Int: Int]) {
        if heapArr.count < topK {
            heapArr.append(dict)
            siftUp(heapArr.count - 1)
        } else {
            if !compare(dict, heapArr[0]) {
                heapArr.append(dict)
                heapArr.swapAt(0, heapArr.count - 1)
                heapArr.removeLast()
                siftDown(0)
            }
        }
    }
    
    private func siftUp(_ index: Int) {
        if index < 1 {
            return
        }
        let parent = (index - 1) / 2
        if compare(heapArr[index], heapArr[parent]) {
            heapArr.swapAt(parent, index)
            siftUp(parent)
        }
        
    }
    
    private func siftDown(_ index: Int) {
        var left = index * 2 + 1
        var right = index * 2 + 2
        var parent = index
        
        if left < heapArr.count && !compare(heapArr[parent], heapArr[left]) {
            swap(&parent, &left)
        }
        
        if right < heapArr.count && !compare(heapArr[parent], heapArr[right]) {
            swap(&parent, &right)
        }
        
        if parent != index {
            heapArr.swapAt(parent, index)
            siftDown(parent)
        }
    }
    
    private func compare(_ ele1: [Int: Int], _ ele2: [Int: Int]) -> Bool {
        
        if ele1.first!.value > ele2.first!.value {
            return true
        } else {
            return false
        }
    }
    
}