美文网首页算法
leetcode 973. 最接近原点的 K 个点 三种解法

leetcode 973. 最接近原点的 K 个点 三种解法

作者: 某非著名程序员 | 来源:发表于2020-11-09 19:16 被阅读0次

    1. 解法一:利用系统排序:取前面K个数

    func kClosest(_ points: [[Int]], _ K: Int) -> [[Int]] {
            let arr = points.sorted { (point1, point2) -> Bool in
                let sqrt1 = point1[0]*point1[0]+point1[1]*point1[1]
                let sqrt2 = point2[0]*point2[0]+point2[1]*point2[1]
    
                if sqrt1<sqrt2{
                    return true
                }
                return false
            }
            
            return Array(arr[0..<K])
        }
    

    2.解法二堆排:维护K大小的大顶堆

    func kClosest(_ points: [[Int]], _ K: Int) -> [[Int]] {
            //第一个存放位置;第二个存放值
            var arr = Array.init(repeating: [0,0], count: points.count)
            
            for i in 0..<points.count {
                let point = points[i]
                arr[i][0] = i
                arr[i][1] = point[0]*point[0]+point[1]*point[1]
            }
    
            heap(&arr,K)
            
            var ans = Array.init(repeating: [0,0], count: K)
            for i in 0..<K {
                ans[i] = points[arr[i][0]]
            }
            
            return ans
        }
    
        
        func heap(_ arr: inout [[Int]],_ k:Int) {
            
            //构建大顶堆
            for i in (0...k/2).reversed() {
                adjustMaxTopHeap(&arr, i, k)
            }
    
            for j in (k..<arr.count).reversed() {
                if arr[j][1]<arr[0][1] {
                    swap(&arr, 0, j)
                    adjustMaxTopHeap(&arr, 0, k)
                }
            }
        }
        
        func swap(_ arr:inout [[Int]],_ i:Int,_ j:Int) {
            let temp = arr[j]
            arr[j] = arr[i]
            arr[i] = temp
        }
        
        //调整大顶堆
        func adjustMaxTopHeap(_ array:inout [[Int]], _ parent:Int,_ length:Int) {
            var parentIndex = parent
            let temp = array[parentIndex]
            var child = 2*parentIndex+1//2n+1:左孩子,2n+2:右孩子
            //把最小的数据放在大于孩子节点的位置
            while child<length {
                //取左右孩子节点的最大节点
                if child+1<length && array[child][1]<array[child+1][1]{
                    child += 1
                }
                if temp[1]>array[child][1]{//父节点大于左右孩子节点
                    break
                }
                array[parentIndex] = array[child]
                parentIndex = child
                
                child = 2*child+1
            }
            array[parentIndex] = temp
        }
    

    3.快排:选取第K个元素位置

    func kClosest(_ points: [[Int]], _ k: Int) -> [[Int]] {
            var arr = Array.init(repeating: [0,0], count: points.count)
            
            for i in 0..<points.count {
                let point = points[i]
                arr[i][0] = i
                arr[i][1] = point[0]*point[0]+point[1]*point[1]
            }
            
            var start = 0
            var end = arr.count-1
            var index = quickSort(&arr, start, end)
            while index != k-1 {
                if index>k-1 {
                    end = index-1
                }else{
                    start = index+1
                }
                index = quickSort(&arr,start, end)
            }
            
            var ans = Array.init(repeating: [0,0], count: k)
            for i in 0..<k {
                ans[i] = points[arr[i][0]]
            }
            return ans
        }
        
        func quickSort(_ arr:inout [[Int]],_ start:Int,_ end:Int) -> Int {
            if start >= end {
                return start
            }
            let key = arr[start]
            var start = start
            var end = end
            
            while start<end {
                while start<end && key[1]<=arr[end][1] {
                    end -= 1
                }
                if start<end {
                    arr[start] = arr[end]
                }
                
                while start<end && key[1]>=arr[start][1] {
                    start += 1
                }
                if start<end {
                    arr[end] = arr[start]
                }
                
            }
            arr[start] = key
            return start
        }

    相关文章

      网友评论

        本文标题:leetcode 973. 最接近原点的 K 个点 三种解法

        本文链接:https://www.haomeiwen.com/subject/xnlrbktx.html