IOS 算法(基础篇) ----- 最接近原点的 K 个点

题目: 有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。

输入：points = [[1,3],[-2,2]], K = 1
输出：[[-2,2]]
解释：
(1, 3) 和原点之间的距离为 sqrt(10)，
(-2, 2) 和原点之间的距离为 sqrt(8)，
由于 sqrt(8) < sqrt(10)，(-2, 2) 离原点更近。
我们只需要距离原点最近的 K = 1 个点，所以答案就是 [[-2,2]]。

输入：points = [[3,3],[5,-1],[-2,4]], K = 2
输出：[[3,3],[-2,4]]（答案 [[-2,4],[3,3]] 也会被接受。）

解题思路

给定一个点, 求距离原点距离, 其实就是求由x轴坐标, y轴坐标构成直角三角形斜边的长度

example

由勾股定理可得, 直角三角形有 c^2 = a^2 + b^2 (a,b直角边,斜边c)

由于我们只需找到最小K个, 固找到 a^2 + b^2 最小的K个即可(这里留意下没必要多做开方运算, 因为我们只是需要找到点)

所以解题思路
1.按 a^2 + b^2 从小到大排序
2.排序完, 截取前K个元素

2行代码即可

自带排序法

    func kClosest(_ points: [[Int]], _ K: Int) -> [[Int]] {
        var temp:[[Int]] = points.sorted(by: {v1, v2 in v1[0] * v1[0] + v1[1] * v1[1] <= v2[0] * v2[0] + v2[1] * v2[1]})
        return Array(temp.prefix(K))
    }

①平方那里可以用pow幂函数计算, 不过要留意一下转换问题
②判断要用小于等于, 因为会有值相等情况

上面方法我们可以看到, 用时和内存消耗比较大
这边我们手写改善下, 用经典快速排序处理下这个问题

经典快速排序

    func kClosest(_ points: [[Int]], _ K: Int) -> [[Int]] {
        var temp:[[Int]] = points
        quickSort(data: &temp, low: 0, high: temp.count-1)
        return Array(temp.prefix(K))
        
    }
    
    func quickSort(data:inout [[Int]], low:Int, high: Int){
      
        if low > high {
            return
        }
        let sortIndex = partition(data: &data, low: low, high: high)
        quickSort(data: &data, low: low, high: sortIndex-1)
        quickSort(data: &data, low: sortIndex+1, high: high)
    }
    
    func partition( data:inout [[Int]],low:Int,high:Int) -> Int {

         let root = data[high]
         var index = low
         for i in low...high {
            
            let data_i = data[i],
                c1 = data_i[0] * data_i[0] + data_i[1] * data_i[1],
                c2 = root[0] * root[0] + root[1] * root[1]
            if c1 < c2 {
                if i != index {
                    data.swapAt(i, index)
                }
                index = index+1
            }
         }

         if high != index {
            data.swapAt(high, index)
         }
         return index
     }

题目来源：力扣（LeetCode）感谢力扣爸爸 :)
IOS 算法合集地址