算法

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

2020-11-09  本文已影响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
    }
上一篇下一篇

猜你喜欢

热点阅读