★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10744606.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
We are given a matrix with R rows and C columns has cells with integer coordinates (r, c), where 0 <= r < R and 0 <= c < C.
Additionally, we are given a cell in that matrix with coordinates (r0, c0).
Return the coordinates of all cells in the matrix, sorted by their distance from (r0, c0) from smallest distance to largest distance. Here, the distance between two cells (r1, c1) and (r2, c2) is the Manhattan distance, |r1 - r2| + |c1 - c2|. (You may return the answer in any order that satisfies this condition.)
Example 1:
Input: R = 1, C = 2, r0 = 0, c0 = 0
Output: [[0,0],[0,1]]
Explanation: The distances from (r0, c0) to other cells are: [0,1]
Example 2:
Input: R = 2, C = 2, r0 = 0, c0 = 1
Output: [[0,1],[0,0],[1,1],[1,0]]
Explanation: The distances from (r0, c0) to other cells are: [0,1,1,2]
The answer [[0,1],[1,1],[0,0],[1,0]] would also be accepted as correct.
Example 3:
Input: R = 2, C = 3, r0 = 1, c0 = 2
Output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
Explanation: The distances from (r0, c0) to other cells are: [0,1,1,2,2,3]
There are other answers that would also be accepted as correct, such as [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]].
Note:
1 <= R <= 1001 <= C <= 1000 <= r0 < R0 <= c0 < C
给出 R 行 C 列的矩阵，其中的单元格的整数坐标为 (r, c)，满足 0 <= r < R 且 0 <= c < C。
另外，我们在该矩阵中给出了一个坐标为 (r0, c0) 的单元格。
返回矩阵中的所有单元格的坐标，并按到 (r0, c0) 的距离从最小到最大的顺序排，其中，两单元格(r1, c1) 和 (r2, c2) 之间的距离是曼哈顿距离，|r1 - r2| + |c1 - c2|。（你可以按任何满足此条件的顺序返回答案。）
示例 1：
输入：R = 1, C = 2, r0 = 0, c0 = 0 输出：[[0,0],[0,1]] 解释：从 (r0, c0) 到其他单元格的距离为：[0,1]
示例 2：
输入：R = 2, C = 2, r0 = 0, c0 = 1 输出：[[0,1],[0,0],[1,1],[1,0]] 解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2] [[0,1],[1,1],[0,0],[1,0]] 也会被视作正确答案。
示例 3：
输入：R = 2, C = 3, r0 = 1, c0 = 2 输出：[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]] 解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2,2,3] 其他满足题目要求的答案也会被视为正确，例如 [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]]。
提示：
1 <= R <= 1001 <= C <= 1000 <= r0 < R0 <= c0 < C
264ms
1 lass Solution { 2 3 func allCellsDistOrder(_ R: Int, _ C: Int, _ r0: Int, _ c0: Int) -> [[Int]] { 4 var distances = [Int: [[Int]]]() 5 var q = Queue<(Int, Int)>() 6 var visited = Set<Int>() 7 q.push((r0 * C + c0, 0)) 8 visited.insert(r0 * C + c0) 9 while !q.isEmpty { 10 let (node, dist) = q.pop() 11 let row = node / C 12 let col = node % C 13 distances[dist, default: []].append([row, col]) 14 if row > 0 && !visited.contains( (row - 1) * C + col ) { 15 q.push(((row - 1) * C + col, dist + 1)) 16 visited.insert((row - 1) * C + col) 17 } 18 if row + 1 < R && !visited.contains( (row + 1) * C + col ) { 19 q.push(((row + 1) * C + col, dist + 1)) 20 visited.insert((row + 1) * C + col) 21 } 22 23 if col > 0 && !visited.contains( row * C + col - 1) { 24 q.push((row * C + col - 1, dist + 1)) 25 visited.insert(row * C + col - 1) 26 } 27 if col + 1 < C && !visited.contains( row * C + col + 1) { 28 q.push((row * C + col + 1, dist + 1)) 29 visited.insert(row * C + col + 1) 30 } 31 } 32 let keys = distances.keys.sorted() 33 var res = [[Int]]() 34 for key in keys { 35 res += distances[key]! 36 } 37 return res 38 } 39 } 40 41 struct Queue<T> { 42 var arr: [T] = [] 43 var head = 0 44 45 mutating func push(_ val: T) { 46 arr.append(val) 47 } 48 49 mutating func pop() -> T { 50 let res = arr[head] 51 head += 1 52 return res 53 } 54 55 var isEmpty: Bool { 56 return head == arr.count 57 } 58 }
300ms
1 class Solution { 2 func allCellsDistOrder(_ R: Int, _ C: Int, _ r0: Int, _ c0: Int) -> [[Int]] { 3 var res: [([Int], Int)] = [] 4 for r in (0..<R) { 5 for c in (0..<C) { 6 res.append(([r,c],abs(r - r0)+abs(c - c0))) 7 } 8 } 9 10 var tt = res.sorted{$0.1<$1.1} 11 var rr: [[Int]] = [] 12 for r in tt { 13 rr.append(r.0) 14 } 15 16 return rr 17 } 18 }
316ms
1 class Solution { 2 3 func allCellsDistOrder(_ R: Int, _ C: Int, _ r0: Int, _ c0: Int) -> [[Int]] { 4 if R == 0 || C == 0{ 5 return [[Int]]() 6 } 7 8 var ar = [[Int]]() 9 10 for r in 0..<R{ 11 for c in 0..<C{ 12 var left = abs(r0 - r) 13 var right = abs(c0 - c) 14 var sum = left + right 15 ar.append([sum, r, c]) 16 } 17 } 18 var res = [[Int]]() 19 ar = ar.sorted{$0[0] < $1[0]} 20 for i in ar{ 21 res.append(Array(i[1...2])) 22 } 23 return res 24 } 25 }
320ms
1 class Solution { 2 struct Node { 3 var distance: Int 4 var coordinate: [Int] 5 init(_ distance: Int, _ coordinate: [Int]) { 6 self.distance = distance 7 self.coordinate = coordinate 8 } 9 } 10 11 func allCellsDistOrder(_ R: Int, _ C: Int, _ r0: Int, _ c0: Int) -> [[Int]] { 12 13 var nodes = [Node]() 14 for i in 0..<R { 15 for j in 0..<C { 16 let distance = abs(r0-i) + abs(c0-j) 17 nodes.append(Node(distance, [i, j])) 18 } 19 } 20 21 nodes.sort(by: { $0.distance <= $1.distance}) 22 return nodes.map { $0.coordinate } 23 } 24 }
364ms
1 class Solution { 2 func allCellsDistOrder(_ R: Int, _ C: Int, _ r0: Int, _ c0: Int) -> [[Int]] { 3 let maxRDist = max(R - r0, r0 - 0) 4 let maxCDist = max(C - c0, c0 - 0) 5 let maxDist = maxRDist + maxCDist 6 var dist = 0 7 var allCoors = [[Int]]() 8 var set = Set<[Int]>() 9 set.insert([r0, c0]) 10 allCoors += Array(set) 11 12 while dist < maxDist { 13 var s = Set<[Int]>() 14 // print("====================\(set)") 15 for coor in set { 16 s.formUnion(coors(R, C, r0, c0, coor[0], coor[1], dist)) 17 } 18 // print("==========>>>>>>>>>>>>\(s)") 19 allCoors += Array(s) 20 set = s 21 dist += 1 22 } 23 return allCoors 24 } 25 26 func coors(_ R: Int, _ C: Int, _ r0: Int, _ c0: Int, _ r: Int, _ c: Int, _ dist: Int) -> Set<[Int]> { 27 let vr = r - r0 28 let vc = c - c0 29 let dr = vr != 0 ? vr / abs(vr) : 0 30 let dc = vc != 0 ? vc / abs(vc) : 0 31 var set = Set<[Int]>() 32 var newRs: [Int] = [] 33 var newCs: [Int] = [] 34 if dr == 0 { 35 if r + 1 < R, abs(r + 1 - r0) > abs(vr) { 36 newRs.append(r + 1) 37 } 38 if r - 1 >= 0, abs(r - 1 - r0) > abs(vr) { 39 newRs.append(r - 1) 40 } 41 } else if r + dr < R, r + dr >= 0 { 42 newRs.append(r + dr) 43 } 44 for newR in newRs { 45 set.insert([newR, c]) 46 } 47 if dc == 0 { 48 if c + 1 < C, abs(c + 1 - c0) > abs(vc) { 49 newCs.append(c + 1) 50 } 51 if c - 1 >= 0, abs(c - 1 - c0) > abs(vc) { 52 newCs.append(c - 1) 53 } 54 } else if c + dc < C, c + dc >= 0 { 55 newCs.append(c + dc) 56 } 57 for newC in newCs { 58 set.insert([r, newC]) 59 } 60 return set 61 } 62 }
384ms
1 class Solution { 2 func allCellsDistOrder(_ R: Int, _ C: Int, _ r0: Int, _ c0: Int) -> [[Int]] { 3 var distances: [[Int]] = Array(repeating: Array(repeating: 0, count: C), count: R) 4 var result: [[Int]] = [] 5 for r in 0...(R - 1) { 6 for c in 0...(C - 1) { 7 let distance = (c - c0).magnitude + (r - r0).magnitude 8 distances[r][c] = Int(distance) 9 result.append([r,c]) 10 } 11 } 12 13 return result.sorted { distances[$0[0]][$0[1]] < distances[$1[0]][$1[1]] } 14 } 15 }
400ms
1 class Solution { 2 func allCellsDistOrder(_ R: Int, _ C: Int, _ r0: Int, _ c0: Int) -> [[Int]] { 3 var result = [[Int]]() 4 5 for i in 0..<R { 6 for j in 0..<C { 7 result.append([i,j]) 8 } 9 } 10 11 return result.sorted { distance($0[0], $0[1], r0, c0) < distance($1[0], $1[1], r0, c0 )} 12 } 13 14 private func distance(_ R1: Int, _ C1: Int, _ R0: Int, _ C0: Int) -> Int { 15 return abs(R0-R1) + abs(C0-C1) 16 } 17 }
Runtime: 480 ms
Memory Usage: 20.5 MB
1 class Solution { 2 func allCellsDistOrder(_ R: Int, _ C: Int, _ r0: Int, _ c0: Int) -> [[Int]] { 3 //优先队列 4 var q = Heap<(Int,[Int])>.init { (f, s) -> Bool in 5 return f.0 < s.0 6 } 7 8 for i in 0..<R 9 { 10 for j in 0..<C 11 { 12 q.insert((getManhattan([r0,c0],[i,j]),[i,j])) 13 } 14 } 15 var res:[[Int]] = [[Int]]() 16 while(!q.isEmpty) 17 { 18 res.append(q.remove()!.1) 19 } 20 return res 21 } 22 23 func getManhattan(_ p1:[Int],_ p2:[Int]) -> Int 24 { 25 return Int(abs(Double(p1[0] - p2[0])) + abs(Double(p1[1] - p2[1]))) 26 } 27 } 28 29 public struct Heap<T> { 30 public var nodes = [T]() 31 private var orderCriteria: (T, T) -> Bool 32 33 public init(sort: @escaping (T, T) -> Bool) { 34 orderCriteria = sort 35 } 36 37 public init(array: [T], sort: @escaping (T, T) -> Bool) { 38 self.orderCriteria = sort 39 configureHeap(from: array) 40 } 41 42 public var isEmpty: Bool { 43 return nodes.isEmpty 44 } 45 46 public var count: Int { 47 return nodes.count 48 } 49 50 public mutating func configureHeap(from array: [T]) { 51 nodes = array 52 for i in stride(from: nodes.count / 2 - 1, through: 0, by: -1) { 53 shiftDown(i) 54 } 55 } 56 57 public mutating func reset() { 58 for i in stride(from: nodes.count / 2 - 1, through: 0, by: -1) { 59 shiftDown(i) 60 } 61 } 62 63 @inline(__always) internal func parentIndex(ofIndex index: Int) -> Int { 64 return (index - 1) / 2 65 } 66 67 @inline(__always) internal func leftChildIndex(ofIndex index: Int) -> Int { 68 return index * 2 + 1 69 } 70 71 @inline(__always) internal func rightChildIndex(ofIndex index: Int) -> Int { 72 return index * 2 + 2 73 } 74 75 public func peek() -> T? { 76 return nodes.first 77 } 78 79 internal mutating func shiftUp(_ index: Int) { 80 var childIndex = index 81 let child = nodes[childIndex] 82 var parentIndex = self.parentIndex(ofIndex: index) 83 while childIndex > 0 && orderCriteria(child, nodes[parentIndex]) { 84 nodes[childIndex] = nodes[parentIndex] 85 childIndex = parentIndex 86 parentIndex = self.parentIndex(ofIndex: childIndex) 87 } 88 nodes[childIndex] = child 89 } 90 91 internal mutating func shiftDown(from index: Int, until endIndex: Int) { 92 let leftChildIndex = self.leftChildIndex(ofIndex: index) 93 let rightChildIndex = self.rightChildIndex(ofIndex: index) 94 95 var first = index 96 if leftChildIndex < endIndex && orderCriteria(nodes[leftChildIndex], nodes[first]) { 97 first = leftChildIndex 98 } 99 if rightChildIndex < endIndex && orderCriteria(nodes[rightChildIndex], nodes[first]) { 100 first = rightChildIndex 101 } 102 if first == index { 103 return 104 } 105 nodes.swapAt(index, first) 106 shiftDown(from: first, until: endIndex) 107 } 108 109 internal mutating func shiftDown(_ index: Int) { 110 shiftDown(from: index, until: nodes.count) 111 } 112 113 public mutating func insert(_ value: T) { 114 nodes.append(value) 115 shiftUp(nodes.count - 1) 116 } 117 118 public mutating func insert<S: Sequence>(_ sequence:S) where S.Iterator.Element == T { 119 for value in sequence { 120 insert(value) 121 } 122 } 123 124 public mutating func replace(index i: Int, value: T) { 125 guard i < nodes.count else { 126 return 127 } 128 remove(at: i) 129 insert(value) 130 } 131 132 @discardableResult 133 public mutating func remove() -> T? { 134 guard !nodes.isEmpty else { 135 return nil 136 } 137 if nodes.count == 1 { 138 return nodes.removeLast() 139 } else { 140 let value = nodes[0] 141 nodes[0] = nodes.removeLast() 142 shiftDown(0) 143 return value 144 } 145 } 146 147 @discardableResult 148 public mutating func remove(at index: Int) -> T? { 149 guard index < nodes.count else { return nil} 150 let size = nodes.count - 1 151 if index != size { 152 nodes.swapAt(index, size) 153 shiftDown(from: index, until: size) 154 shiftUp(index) 155 } 156 return nodes.removeLast() 157 } 158 159 public mutating func sort() -> [T] { 160 for i in stride(from: self.nodes.count - 1, to: 0, by: -1) { 161 nodes.swapAt(0, i) 162 shiftDown(from: 0, until: i) 163 } 164 return nodes 165 } 166 }