★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）➤博客园地址：山青咏芝（）➤GitHub地址：➤原文地址： ➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the k lists.
We define the range [a,b] is smaller than range [c,d] if b-a < d-c or a < c if b-a == d-c.
Example 1:
Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]Output: [20,24]Explanation: List 1: [4, 10, 15, 24,26], 24 is in range [20,24].List 2: [0, 9, 12, 20], 20 is in range [20,24].List 3: [5, 18, 22, 30], 22 is in range [20,24].
Note:
- The given list may contain duplicates, so ascending order means >= here.
- 1 <=
k<= 3500 - -105 <=
value of elements<= 105. - For Java users, please note that the input type has been changed to List<List<Integer>>. And after you reset the code template, you'll see this point.
你有 k 个升序排列的整数数组。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。
示例 1:
输入:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]输出: [20,24]解释: 列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。
注意:
- 给定的列表可能包含重复元素，所以在这里升序表示 >= 。
- 1 <=
k<= 3500 - -105 <=
元素的值<= 105 - 对于使用Java的用户，请注意传入类型已修改为List<List<Integer>>。重置代码模板后可以看到这项改动。
344ms
1 class Solution { 2 func smallestRange(_ nums: [[Int]]) -> [Int] { 3 var point2Lists = [Int: [Int]]() 4 for i in 0.. n - m {28 ret = [m, n]29 }30 for l in lists {31 if counter[l] == 1 {32 coveredLists -= 133 }34 counter[l] -= 135 }36 i += 137 }38 }39 40 return ret41 }42 } Runtime: 432 ms
Memory Usage: 21.8 MB
1 class Solution { 2 func smallestRange(_ nums: [[Int]]) -> [Int] { 3 var nums = nums 4 var res:[Int] = [Int]() 5 var v:[[Int]] = [[Int]]() 6 var m:[Int:Int] = [Int:Int]() 7 for i in 0.. Bool in15 if a[0] == b[0]16 {17 return a[1] < b[1]18 }19 else 20 {21 return a[0] <= b[0]22 } 23 })24 var left:Int = 025 var n:Int = v.count26 var k:Int = nums.count27 var cnt:Int = 028 var diff:Int = Int.max29 for right in 0.. v[right][0] - v[left][0]39 {40 diff = v[right][0] - v[left][0]41 res = [v[left][0], v[right][0]]42 }43 44 m[v[left][1],default:0] -= 1 45 if m[v[left][1]] == 046 {47 cnt -= 148 }49 left += 150 }51 }52 return res53 }54 } 768ms
1 /* Solution Space */ 2 3 class Solution 4 { 5 6 func smallestRange( _ nums: [ [ Int ] ] ) -> [ Int ] 7 { 8 9 var traversalsHeap: BinaryHeap< ArrayTraversal > = BinaryHeap< ArrayTraversal >( 10 { 11 return ( $0.currentValue <= $1.currentValue ) 12 } 13 ) 14 15 var currentMax: Int = Int.min 16 17 for array in nums 18 { 19 if array.count > 0 20 { 21 22 let newTraversal: ArrayTraversal = ArrayTraversal( array ) 23 24 traversalsHeap.insertElement( newTraversal ) 25 26 currentMax = max( currentMax, newTraversal.currentValue ) 27 28 } 29 } 30 31 guard traversalsHeap.getSize() > 0 32 else 33 { 34 return [] 35 } 36 37 var minSize: Int = Int.max 38 39 var minStart: Int = -1 40 var minEnd: Int = -1 41 42 while true 43 { 44 45 let minTraversal: ArrayTraversal = traversalsHeap.deleteTopElement()! 46 47 let currentMin: Int = minTraversal.currentValue 48 let currentSize: Int = ( currentMax - currentMin ) 49 50 if currentSize < minSize 51 { 52 53 minSize = currentSize 54 55 minStart = currentMin 56 minEnd = currentMax 57 58 } 59 60 if minTraversal.getNextValue() 61 { 62 63 currentMax = max( currentMax, minTraversal.currentValue ) 64 65 traversalsHeap.insertElement( minTraversal ) 66 67 } 68 else 69 { 70 break 71 } 72 } 73 return [ minStart, minEnd ] 74 75 } 76 } 77 78 /* Binary Heap Type */ 79 80 open class BinaryHeap< Type > 81 { 82 83 /* Heap Array */ 84 private var heapArray: [ Type ] 85 86 /* In Order Function */ 87 private let inOrder: ( _ a: Type, _ b: Type ) -> Bool 88 89 /* Initializer */ 90 91 public init( _ inOrder: @escaping ( _ a: Type, _ b: Type ) -> Bool ) 92 { 93 94 self.heapArray = [ Type ]() 95 96 self.inOrder = inOrder 97 98 } 99 100 /* Get Size */101 102 open func getSize() -> Int103 {104 105 return ( heapArray.count )106 107 }108 109 /* Get Tale */110 111 private func getTale() -> Int112 {113 114 return ( heapArray.count - 1 )115 116 }117 118 /* Get Parent */119 120 private func getParent( _ nodePosition: Int ) -> Int?121 {122 123 if nodePosition <= 0124 {125 return nil126 }127 128 let parentPosition: Int = ( ( nodePosition - 1 ) / 2 )129 130 return parentPosition131 132 }133 134 /* Get Left Child */135 136 private func getLeftChild( _ nodePosition: Int ) -> Int?137 {138 139 let childPosition = ( nodePosition * 2 ) + 1140 141 if childPosition <= getTale()142 {143 return childPosition144 }145 else146 {147 return nil148 }149 150 }151 152 /* Get Right Child */153 154 private func getRightChild( _ nodePosition: Int ) -> Int?155 {156 157 let childPosition = ( nodePosition * 2 ) + 2158 159 if childPosition <= getTale()160 {161 return childPosition162 }163 else164 {165 return nil166 }167 168 }169 170 /* Insert Element */171 172 open func insertElement( _ element: Type )173 {174 175 heapArray.append( element )176 177 var traversal1 = getTale()178 var goingUp = true179 180 while goingUp181 {182 183 if let parent = getParent( traversal1 )184 {185 186 if( !inOrder( heapArray[ parent ], heapArray[ traversal1 ] ) )187 {188 189 let temp = heapArray[ traversal1 ]190 heapArray[ traversal1 ] = heapArray[ parent ]191 heapArray[ parent ] = temp192 193 traversal1 = parent194 195 }196 else197 {198 goingUp = false199 }200 201 }202 else203 {204 goingUp = false205 }206 207 }208 209 }210 211 /* Get Top Element */212 213 open func getTopElement() -> Type?214 {215 216 if getSize() == 0217 {218 return nil219 }220 else221 {222 return heapArray[ 0 ]223 }224 225 }226 227 /* Delete Top Element */228 229 open func deleteTopElement() -> Type?230 {231 232 if getSize() == 0233 {234 return nil235 }236 237 let value = getTopElement()238 239 heapArray[ 0 ] = heapArray[ getTale() ]240 heapArray.removeLast()241 242 if( getSize() > 1 )243 {244 245 var traversal = 0246 var goingDown = true247 248 while( goingDown )249 {250 251 var topChild: Int? = nil252 253 if let child = getLeftChild( traversal )254 {255 256 topChild = child257 258 }259 260 if let child = getRightChild( traversal )261 {262 263 if( topChild == nil || !inOrder( heapArray[ topChild! ], heapArray[ child ] ) )264 {265 266 topChild = child267 268 }269 270 }271 272 if( topChild != nil && !inOrder( heapArray[ traversal ], heapArray[ topChild! ] ) )273 {274 275 let temp = heapArray[ traversal ]276 heapArray[ traversal ] = heapArray[ topChild! ]277 heapArray[ topChild! ] = temp278 279 traversal = topChild!280 281 }282 else283 {284 goingDown = false285 }286 287 }288 289 }290 291 return value292 293 }294 295 }296 297 /* Array Traversal Type */298 299 class ArrayTraversal300 {301 302 private let array: [ Int ]303 private var currentIndex: Int304 305 private(set) var currentValue: Int306 307 init( _ array: [ Int ] )308 {309 310 self.array = array 311 self.currentIndex = 0312 313 self.currentValue = array[ currentIndex ]314 315 }316 317 func getNextValue() -> Bool318 {319 320 if currentIndex == ( array.count - 1 )321 { 322 return false 323 }324 325 currentIndex += 1326 327 currentValue = array[ currentIndex ]328 329 return true330 331 }332 333 } 1392ms
1 class Solution { 2 func smallestRange(_ nums: [[Int]]) -> [Int] { 3 var res = Array.init(repeating: 0, count: 2) 4 5 var m = [Int:Int]() 6 var items = [[Int]]() 7 var cnt = 0 8 for i in 0.. items[right].first! - items[left].first! {28 diff = items[right].first! - items[left].first!29 res = [items[left].first!, items[right].first!]30 }31 32 m[items[left].last!] = m[items[left].last!]! - 133 if (m[items[left].last!] == 0) {cnt -= 1}34 left += 135 }36 37 right += 138 }39 40 return res41 } 42 } 7412ms
1 class Solution { 2 func smallestRange(_ nums: [[Int]]) -> [Int] { 3 var pointers = Array(repeating: 0, count: nums.count) 4 var minDiff = Int.max 5 var output = [Int.min, Int.max] 6 while true { 7 var minIndex = 0 8 var maxValue = Int.min 9 var minValue = Int.max10 for i in 0 ..< pointers.count {11 let value = nums[i][pointers[i]] 12 maxValue = max(maxValue, value)13 if value < minValue {14 minIndex = i15 minValue = value16 } 17 }18 let diff = maxValue - minValue19 if diff < minDiff {20 minDiff = diff21 output[0] = minValue22 output[1] = maxValue23 }24 pointers[minIndex] += 125 if pointers[minIndex] > nums[minIndex].count - 1 {26 return output27 }28 }29 return []30 }31 }