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
}