大佬教程收集整理的这篇文章主要介绍了[Swift]LeetCode703. 数据流中的第K大元素 | Kth Largest Element in a Stream，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order,not the kth disTinct element.
Your KthLargest class will have a constructor which accepts an Integer k and an Integer array nums,which contains initial elements from the stream. For each call to the method KthLargest.add,return the element represenTing the kth largest element in the stream.
Example:
int k = 3; int[] arr = [4,5,8,2]; KthLargest kthLargest = new KthLargest(3,arr); kthLargest.add(3); // returns 4 kthLargest.add(5); // returns 5 kthLargest.add(10); // returns 5 kthLargest.add(9); // returns 8 kthLargest.add(4); // returns 8
Note:
You may assume that nums‘ length ≥ k-1 and k ≥ 1.
设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。
你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。
示例:
int k = 3; int[] arr = [4,arr); kthLargest.add(3); // returns 4 kthLargest.add(5); // returns 5 kthLargest.add(10); // returns 5 kthLargest.add(9); // returns 8 kthLargest.add(4); // returns 8
说明:
你可以假设 nums 的长度≥ k-1 且k ≥ 1。
188ms
1 class KthLargest { 2 var queue: PriorityQueue 3 var k: Int 4 5 init(_ k: Int,_ nums: [Int]) { 6 self.queue = PriorityQueue() 7 self.k = k 8 9 for val in nums { 10 self.queue.enqueue(val) 11 } 12 13 var temp = nums.count - k 14 while temp > 0 { 15 self.queue.dequeue() 16 temp -= 1 17 } 18 } 19 20 func add(_ val: int) -> Int { 21 queue.enqueue(val) 22 if queue.array.count > k { 23 queue.dequeue() 24 } 25 return queue.peek()! 26 } 27 } 28 29 struct PriorityQueue { 30 var array = [Int]() 31 32 func peek() -> Int? { 33 return array.first 34 } 35 36 mutaTing func enqueue(_ num: int) { 37 array.append(num) 38 siftUp() 39 } 40 41 mutaTing func dequeue() { 42 array.swapAt(0,array.count - 1) 43 array.removeLast() 44 siftDown() 45 } 46 47 mutaTing func siftDown() { 48 var pIndex = 0 49 var sLIndex = 0 50 var sRIndex = 0 51 var index = 0 52 53 while pIndex * 2 + 1 <= array.count - 1 { 54 sLIndex = pIndex * 2 + 1 55 sRIndex = pIndex * 2 + 2 56 index = pIndex 57 58 if arraY[pIndex] > arraY[sLIndex] { 59 index = sLIndex 60 } 61 62 if sRIndex <= array.count - 1 && arraY[index] > arraY[sRIndex] { 63 index = sRIndex 64 } 65 66 if (pIndex != indeX) { 67 array.swapAt(pIndex,indeX) 68 pIndex = index 69 } else { 70 return 71 } 72 } 73 } 74 75 mutaTing func siftUp() { 76 var pIndex = 0 77 var sIndex = array.count - 1 78 79 while sIndex != 0 { 80 pIndex = (sIndex - 1) / 2 81 if (arraY[sIndex] < arraY[pIndex]) { 82 array.swapAt(sIndex,pIndeX) 83 sIndex = pIndex 84 } else { 85 return 86 } 87 } 88 } 89 }
204ms
1 class KthLargest { 2 3 let k:Int 4 let heap = MinHeap() 5 6 init(_ k: Int,_ nums: [Int]) { 7 self.k = k 8 for n in nums{ 9 self.heap.add(n) 10 if self.heap.count > k{ 11 _ = self.heap.poll() 12 } 13 } 14 } 15 16 func add(_ val: int) -> Int { 17 if self.heap.count < k{ 18 self.heap.add(val) 19 return self.heap.peek()! 20 } 21 if val <= self.heap.peek()!{ 22 return self.heap.peek()! 23 } 24 _ = self.heap.poll() 25 self.heap.add(val) 26 return self.heap.peek()! 27 } 28 } 29 30 class MinHeap{ 31 32 var data:[Int] = [Int]() 33 34 func parenTindex(_ index:int) -> Int{ 35 return (index - 1) / 2 36 } 37 38 func leftChildIndex(_ index:int) -> Int{ 39 return index * 2 + 1 40 } 41 42 func rightChildIndex(_ index:int) -> Int{ 43 return index * 2 + 2 44 } 45 46 func parent(_ index:int) -> Int{ 47 return self.data[self.parenTindex(indeX)] 48 } 49 50 func leftChild(_ index:int) -> Int{ 51 return self.data[self.leftChildIndex(indeX)] 52 } 53 54 func rightChild(_ index:int) -> Int{ 55 return self.data[self.rightChildIndex(indeX)] 56 } 57 58 func hasParent(_ index:int) -> Bool{ 59 return self.parenTindex(indeX) >= 0 60 } 61 62 func hasLeftChild(_ index:int) -> Bool{ 63 return self.leftChildIndex(indeX) < self.data.count 64 } 65 66 func hasRightChild(_ index:int) -> Bool{ 67 return self.rightChildIndex(indeX) < self.data.count 68 } 69 70 func peek() -> Int?{ 71 return self.data.first 72 } 73 74 func poll() -> Int{ 75 let first = self.data[0] 76 self.data[0] = self.data[self.data.count - 1] 77 self.data.removeLast() 78 if self.data.count > 1{ 79 self.heapifyDown() 80 } 81 return first 82 } 83 84 func add(_ item:int){ 85 self.data.append(item) 86 if self.data.count > 1{ 87 self.heapifyUp() 88 } 89 } 90 91 func heapifyUp(){ 92 var currenTindex = self.data.count - 1 93 while self.hasParent(currenTindeX) && self.parent(currenTindeX) > self.data[currenTindex]{ 94 self.data.swapAt(currenTindex,self.parenTindex(currenTindeX)) 95 currenTindex = self.parenTindex(currenTindeX) 96 } 97 } 98 99 func heapifyDown(){ 100 var currenTindex = 0 101 while self.hasLeftChild(currenTindeX){ 102 var smallerChildIndex = self.leftChildIndex(currenTindeX) 103 if self.hasRightChild(currenTindeX) 104 && self.rightChild(currenTindeX) < self.leftChild(currenTindeX){ 105 smallerChildIndex = self.rightChildIndex(currenTindeX) 106 } 107 if self.data[currenTindex] > self.data[smallerChildIndex]{ 108 self.data.swapAt(currenTindex,smallerChildIndeX) 109 currenTindex = smallerChildIndex 110 }else{ 111 break 112 } 113 } 114 } 115 116 var count:Int{ 117 return self.data.count 118 } 119 }
1 class KthLargest { 2 var q: Heap 3 var k:Int = 0 4 5 init(_ k: Int,_ nums: [Int]) { 6 self.k = k 7 q = Heap(sort: <) 8 for n in nums 9 { 10 add(n) 11 } 12 } 13 14 func add(_ val: int) -> Int { 15 if q.count < k 16 { 17 q.push(val) 18 } 19 else if (q.peek() != nil && q.peek()! < val) 20 { 21 q.pop() 22 q.push(val) 23 } 24 return q.peek()! 25 } 26 } 27 28 public struct Heap { 29 var elements: [Int] = [] 30 let sort: (Int,int) -> Bool 31 var isEmpty: Bool { 32 return self.elements.isEmpty 33 } 34 35 var count: Int { 36 return self.elements.count 37 } 38 39 func peek() -> Int? { 40 return elements.first 41 } 42 43 init(sort: @escaping (Int,int) -> Bool,elements: [Int] = []) { 44 self.sort = sort 45 self.elements = elements 46 47 if !elements.isEmpty { 48 for i in Stride(from: elements.count/2 - 1,through: 0,by: -1) { 49 siftDown(from: i) 50 } 51 } 52 } 53 54 mutaTing func siftDown(from index: int) { 55 var parent = index 56 while true { 57 let left = lefTindex(of: parent) 58 let right = righTindex(of: parent) 59 var candidate = parent 60 if left < count && sort(elements[left],elements[candidate]) { 61 candidate = left 62 } 63 if right < count && sort(elements[right],elements[candidate]) { 64 candidate = right 65 } 66 if candidate == parent { 67 return 68 } 69 elements.swapAt(parent,candidatE) 70 parent = candidate 71 } 72 } 73 74 mutaTing func siftUp(from index: int) { 75 var child = index 76 var parent = parenTindex(of: child) 77 while child > 0 && sort(elements[child],elements[parent]) { 78 elements.swapAt(child,parent) 79 child = parent 80 parent = parenTindex(of: child) 81 } 82 } 83 84 mutaTing func push(_ element: int) { 85 elements.append(element) 86 siftUp(from: count-1) 87 } 88 89 mutaTing func pop() -> Int? { 90 guard !isEmpty else { return nil } 91 elements.swapAt(0,count-1) 92 defer { 93 siftDown(from: 0) 94 } 95 return elements.popLast() 96 } 97 98 func lefTindex(of index: int) -> Int { 99 return (2 * indeX) + 1 100 } 101 102 func righTindex(of index: int) -> Int { 103 return (2 * indeX) + 2 104 } 105 106 func parenTindex(of index: int) -> Int { 107 return (index - 1) / 2 108 } 109 }
224ms
1 class KthLargest { 2 let minHeap: Heap<Int> 3 let k: Int 4 5 init(_ k: Int,_ nums: [Int]) { 6 minHeap = Heap(elements: nums) 7 self.k = k 8 9 while minHeap.count > k { 10 minHeap.extract() 11 } 12 } 13 14 func add(_ val: int) -> Int { 15 if minHeap.count < k || val > minHeap.peek()! { 16 minHeap.insert(val) 17 } 18 19 if minHeap.count > k { 20 minHeap.extract() 21 } 22 return minHeap.peek()! 23 } 24 } 25 26 27 public class Heap<T: Comparable> { 28 private var elements: [T] = [] 29 private let areInIncreasingOrder: (T,T) -> Bool 30 31 public var count: Int { 32 return elements.count 33 } 34 35 public var isEmpty: Bool { 36 return elements.isEmpty 37 } 38 39 public init(elements: [T] = [],compareWith: @escaping ((T,T) -> Bool) = { $0 < $1 }) { 40 self.elements = elements 41 self.areInIncreasingOrder = compareWith 42 43 let firstLeafIndex = elements.count / 2 44 let lastParenTindex = firstLeafIndex - 1 45 // Only need to bubble down non-leaf nodes (lastParenTindex to 0) 46 for i in Stride(from: lastParenTindex,by: -1) { 47 siftDown(from: i) 48 } 49 } 50 51 public func insert(_ value: T) { 52 elements.append(value) 53 siftUp(from: elements.count - 1) 54 } 55 56 public func peek() -> T? { 57 return elements.first 58 } 59 60 public func extract() -> T? { 61 guard !elements.isEmpty else { return nil } 62 let max = elements.first! 63 elements.swapAt(0,elements.count - 1) 64 elements.removeLast() 65 siftDown(from: 0) 66 return max 67 } 68 69 public func contains(_ element: T) -> Bool { 70 return firsTindex(of: element,starTingAt: 0) != nil 71 } 72 73 public func remove(_ element: T) -> T? { 74 guard let indexOfElement = firsTindex(of: element) else { return nil } 75 76 let lasTindex = elements.count - 1 77 if indexOfElement == lasTindex { 78 return elements.removeLast() 79 } else { 80 elements.swapAt(indexOfElement,lasTindeX) 81 let element = elements.removeLast() 82 83 // May need to either move up or down 84 siftUp(from: indexOfElement) 85 siftDown(from: indexOfElement) 86 87 return element 88 } 89 } 90 91 // MARK: - Privates 92 93 private func leftChildIndex(for parenTindex: int) -> Int { 94 return (2 * parenTindeX) + 1 95 } 96 97 private func rightChildIndex(for parenTindex: int) -> Int { 98 return (2 * parenTindeX) + 2 99 } 100 101 private func parenTindex(for childIndex: int) -> Int { 102 return (childIndex - 1) / 2 103 } 104 105 private func firsTindex(of element: T,starTingAt starTindex: Int = 0) -> Int? { 106 guard starTindex < count else { return nil } 107 108 if element == elements[starTindex] { 109 return starTindex 110 } else if element > elements[starTindex] { 111 return nil // can‘t be in heap 112 } else if let foundIndex = firsTindex(of: element,starTingAt: leftChildIndex(for: starTindeX)) { 113 return foundIndex // need to check both left and right children 114 } else if let foundIndex = firsTindex(of: element,starTingAt: rightChildIndex(for: starTindeX)) { 115 return foundIndex // need to check both left and right children 116 } 117 118 return nil // element was smaller than any element in the heap 119 } 120 121 private func siftUp(from childIndex: int) { 122 let child = elements[childIndex] 123 let parenTindex = self.parenTindex(for: childIndeX) 124 let parent = elements[parenTindex] 125 126 if areInIncreasingOrder(child,parent) { 127 elements.swapAt(parenTindex,childIndeX) 128 siftUp(from: parenTindeX) 129 } 130 } 131 132 private func siftDown(from parenTindex: int) { 133 var maxElemenTindex = parenTindex 134 135 let leftChildIndex = self.leftChildIndex(for: parenTindeX) 136 if leftChildIndex < elements.count && areInIncreasingOrder(elements[leftChildIndex],elements[maxElemenTindex]) { 137 maxElemenTindex = leftChildIndex 138 } 139 140 let rightChildIndex = self.rightChildIndex(for: parenTindeX) 141 if rightChildIndex < elements.count && areInIncreasingOrder(elements[rightChildIndex],elements[maxElemenTindex]) { 142 maxElemenTindex = rightChildIndex 143 } 144 145 if parenTindex == maxElemenTindex { 146 return // base case 147 } else { 148 elements.swapAt(parenTindex,maxElemenTindeX) 149 siftDown(from: maxElemenTindeX) 150 } 151 } 152 }
232ms
1 class KthLargest { 2 3 var nums:[Int] 4 var k:Int 5 6 init(_ k: Int,_ nums: [Int]) { 7 self.k = k 8 self.nums = nums.sorted() 9 } 10 //[-1,5] 11 func add(_ val: int) -> Int { 12 var left = 0 13 var right = nums.count - 1 14 // [2,4,8] 15 while left <= right { 16 var mid = (left + right + 1) / 2 17 if nums[mid] == val { 18 left = mid 19 right = mid - 1 20 } else if nums[mid] > val { 21 right = mid - 1 22 } else { 23 left = mid + 1 24 } 25 } 26 27 nums.insert(val,at: left) 28 return nums[nums.count - k] 29 } 30 }
244ms
1 class KthLargest { 2 3 let maxHeap: Heap 4 let minHeap: Heap 5 let k: Int 6 7 init(_ k: Int,_ nums: [Int]) { 8 self.maxHeap = Heap(type: .max,array: nums) 9 self.minHeap = Heap(type: .min) 10 self.k = k 11 } 12 13 func add(_ val: int) -> Int { 14 if minHeap.count == k { 15 if let top = minHeap.peek() { 16 if top < val { 17 minHeap.insert(val) 18 _ = minHeap.pop() 19 return minHeap.peek()! 20 } else { 21 return top 22 } 23 } 24 } else { 25 maxHeap.insert(val) 26 while minHeap.count < k { 27 let val = maxHeap.pop()! 28 minHeap.insert(val) 29 } 30 31 return minHeap.peek()! 32 } 33 34 return 0 35 } 36 } 37 38 extension KthLargest { 39 class Heap { 40 41 // MARK: - HeapType 42 enum HeapType { 43 case min 44 case max 45 46 func compare(_ a: Int,_ b: int) -> Bool { 47 switch self { 48 case .min: 49 return a < b 50 case .max: 51 return a > b 52 } 53 } 54 } 55 56 // MARK: - Properties & Init 57 var heap: [Int] 58 var type: HeapType 59 60 init(type: HeapType,array: [Int] = []) { 61 self.type = type 62 self.heap = array 63 64 guard !array.isEmpty else { return } 65 66 var i = (heap.count - 1) / 2 67 while i >= 0 { 68 heapify(i) 69 i -= 1 70 } 71 } 72 73 // MARK: - APIs 74 75 var count: Int { 76 return heap.count 77 } 78 79 // O[1] 80 func pop() -> Int? { 81 guard let first = heap.first else { 82 return nil 83 } 84 85 if let last = heap.last { 86 heap[0] = last 87 heapify(0) 88 } 89 90 heap.removeLast() 91 92 return first 93 } 94 95 // O[1] 96 func peek() -> Int? { 97 return heap.first 98 } 99 100 // O[log(n)] 101 func insert(_ val: int) { 102 heap.append(val) 103 siftUp(heap.count - 1) 104 } 105 106 // MARK: - Utilty Methods 107 private func heapify(_ i: int) { 108 var top = i 109 110 if let left = left(i),type.compare(heap[left],heap[top]) { 111 top = left 112 } 113 114 if let right = right(i),type.compare(heap[right],heap[top]) { 115 top = right 116 } 117 118 if top != i { 119 heap.swapAt(i,top) 120 heapify(top) 121 } 122 } 123 124 private func siftUp(_ i: int) { 125 var parent = parenTindex(i) 126 var this = i 127 128 while let p = parent,type.compare(heap[this],heap[p]) { 129 heap.swapAt(p,this) 130 parent = parenTindex(p) 131 this = p 132 } 133 } 134 135 private func parenTindex(_ i: int) -> Int? { 136 guard i > 0 else { return nil } 137 return (i - 1) / 2 138 } 139 140 private func left(_ i: int) -> Int? { 141 let left = i * 2 + 1 142 return left < heap.count ? left : nil 143 } 144 145 private func right(_ i: int) -> Int? { 146 let right = i * 2 + 2 147 return right < heap.count ? right : nil 148 } 149 } 150 }
252ms
1 class KthLargest { 2 3 var minHeap: Heap<Int> 4 var K: Int 5 init(_ k: Int,_ nums: [Int]) { 6 minHeap = Heap<Int>(sort: <,elements: nums) 7 while minHeap.count > k { 8 minHeap.remove() 9 } 10 K = k 11 } 12 13 func add(_ val: int) -> Int { 14 if minHeap.count < K { 15 16 minHeap.insert(val) 17 } else if minHeap.peek()! < val { 18 minHeap.remove() 19 minHeap.insert(val) 20 } 21 return minHeap.peek()! 22 } 23 } 24 25 26 /** 27 * Your KthLargest object will be instantiated and called as such: 28 * let obj = KthLargest(k,nums) 29 * let ret_1: Int = obj.add(val) 30 */ 31 32 struct Heap<Element: Equatable> { 33 var elements: [Element] = [] 34 let sort: (Element,Element) -> Bool 35 init(sort: @escaping (Element,Element) -> Bool, 36 elements: [Element] = []) { // ?? Escaping?? Why 37 self.sort = sort 38 self.elements = elements 39 40 if !elements.isEmpty { 41 for i in Stride(from: elements.count / 2 - 1,by: -1) { 42 siftDown(from: i) 43 } 44 } 45 } 46 47 var isEmpty: Bool { 48 return elements.isEmpty 49 } 50 51 var count: Int { 52 return elements.count 53 } 54 55 func peek() -> Element? { 56 return elements.first 57 } 58 59 func leftChildIndex(ofParentAt index: int) -> Int { 60 return (2 * indeX) + 1 61 } 62 63 func rightChildIndex(ofParentAt index: int) -> Int { 64 return 2 * (index + 1) 65 } 66 67 func parenTindex(ofChildAt index: int) -> Int { 68 return (index - 1) / 2 69 } 70 71 mutaTing func siftDown(from index: int) { 72 var parent = index 73 while true { 74 let left = leftChildIndex(ofParentAt: parent) 75 let right = rightChildIndex(ofParentAt: parent) 76 var candidate = parent 77 if left < count && sort(elements[left],elements[candidate]) { 78 candidate = left 79 } 80 if right < count && sort(elements[right],elements[candidate]) { 81 candidate = right 82 } 83 if candidate == parent { 84 return 85 } 86 elements.swapAt(parent,candidatE) 87 parent = candidate 88 } 89 } 90 91 mutaTing func siftUp(from index: int) { 92 var child = index 93 var parent = parenTindex(ofChildAt: child) 94 while child > 0 && sort(elements[child],elements[parent]) { 95 elements.swapAt(child,parent) 96 child = parent 97 parent = parenTindex(ofChildAt: child) 98 } 99 } 100 101 // Remove 102 // Swap -> Sift Down( compare with two children) 103 mutaTing func remove() -> Element? { 104 guard !isEmpty else { 105 return nil 106 } 107 elements.swapAt(0,count - 1) 108 defer { 109 siftDown(from: 0) 110 } 111 return elements.removeLast() 112 } 113 114 // Insert 115 // Append -> sift(guolv) up 116 mutaTing func insert(_ element: Element) { 117 elements.append(element) 118 siftUp(from: elements.count - 1) 119 } 120 121 func index(of element: Element,starTingAt i: int) -> Int? { 122 if i >= count { 123 return nil 124 } 125 if sort(element,elements[i]) { 126 return nil 127 } 128 if element == elements[i] { 129 return i 130 } 131 if let j = index(of: element,starTingAt: leftChildIndex(ofParentAt: i)) { 132 return j 133 } 134 if let j = index(of: element,starTingAt: rightChildIndex(ofParentAt: i)) { 135 return j 136 } 137 return nil 138 } 139 }
256ms
1 class KthLargest { 2 3 let maxHeap: Heap 4 let minHeap: Heap 5 let k: Int 6 7 init(_ k: Int,this) 130 parent = parenTindex(p) 131 this = p 132 } 133 } 134 135 private func parenTindex(_ i: int) -> Int? { 136 guard i > 0 else { return nil } 137 return (i - 1) / 2 138 } 139 140 private func left(_ i: int) -> Int? { 141 let left = i * 2 + 1 142 return left < heap.count ? left : nil 143 } 144 145 private func right(_ i: int) -> Int? { 146 let right = i * 2 + 2 147 return right < heap.count ? right : nil 148 } 149 } 150 }
344ms
1 class KthLargest { 2 private let k: Int 3 private var count: Int 4 private var minHeap: MinHeap<Int> 5 6 init(_ k: Int,_ nums: [Int]) { 7 self.k = k 8 self.count = 0 9 self.minHeap = MinHeap<Int>() 10 for num in nums { 11 add(num) 12 } 13 } 14 15 @discardableResult 16 func add(_ value: int) -> Int { 17 count += 1 18 19 if count <= k { 20 minHeap.insert(value) 21 return minHeap.min()! 22 } 23 24 if value >= minHeap.min()! { 25 minHeap.delete() 26 minHeap.insert(value) 27 } 28 29 return minHeap.min()! 30 } 31 } 32 33 /** 34 * Your KthLargest object will be instantiated and called as such: 35 * let obj = KthLargest(k,nums) 36 * let ret_1: Int = obj.add(val) 37 */ 38 39 public class Heap<ValueType: Comparable> { 40 41 public private(set) var values: [ValueType] 42 private let debug: Bool 43 44 public init(debug: Bool = false) { 45 values = [] 46 self.debug = debug 47 } 48 49 public var count: Int { 50 return values.count 51 } 52 53 public var isEmpty: Bool { 54 return values.count <= 0 55 } 56 57 private var rootNodeIndex: Int { 58 return 0 59 } 60 61 private var lastNodeIndex: Int { 62 return values.count - 1 63 } 64 65 private func log(_ String: String) { 66 guard debug else { 67 return 68 } 69 70 print(String) 71 } 72 73 func order(parentNodeValue: ValueType,childNodeValue: ValueTypE) -> Bool { 74 return parentNodeValue < childNodeValue 75 } 76 77 private func order(parentNodeIndex: Int,childNodeIndex: int) -> Bool { 78 guard childNodeIndex >= rootNodeIndex && childNodeIndex <= lastNodeIndex else { 79 return true 80 } 81 82 guard parentNodeIndex >= rootNodeIndex && parentNodeIndex <= lastNodeIndex else { 83 return true 84 } 85 86 return order(parentNodeValue: values[parentNodeIndex],childNodeValue: values[childNodeIndex]) 87 } 88 89 // O(log(n)) time 90 public func insert(_ value: ValueTypE) { 91 values.append(value) 92 siftUp() 93 log("[insert] value: \(value)") 94 } 95 96 // O(log(n)) time 97 @discardableResult 98 public func delete() -> ValueType? { 99 guard !isEmpty else { 100 return nil 101 } 102 103 let rootValue = values[rootNodeIndex] 104 swapValuesAt(index1: rootNodeIndex,index2: lastNodeIndeX) 105 values.remove(at: lastNodeIndeX) 106 siftDown() 107 108 log("[delete] value: \(rootvalue)") 109 return rootValue 110 } 111 112 // Constant time 113 public func rootValue() -> ValueType? { 114 guard !isEmpty else { 115 return nil 116 } 117 118 return values[rootNodeIndex] 119 } 120 121 // MARK: Private methods 122 123 // Sift down the root node to the correct position until the heap properties are satisfied 124 private func siftDown() { 125 guard !isEmpty else { 126 return 127 } 128 129 var currentNodeIndex = rootNodeIndex 130 while currentNodeIndex <= lastNodeIndex { 131 let leftNodeIndex = left(of: currentNodeIndeX) 132 let rightNodeIndex = right(of: currentNodeIndeX) 133 134 if order(parentNodeIndex: currentNodeIndex,childNodeIndex: leftNodeIndeX) 135 && order(parentNodeIndex: currentNodeIndex,childNodeIndex: rightNodeIndeX) { 136 // current node is at the correct position 137 break 138 } else if order(parentNodeIndex: leftNodeIndex,childNodeIndex: currentNodeIndeX) 139 && order(parentNodeIndex: leftNodeIndex,childNodeIndex: rightNodeIndeX) { 140 // current node has to swapped with the left node 141 swapValuesAt(index1: currentNodeIndex,index2: leftNodeIndeX) 142 currentNodeIndex = leftNodeIndex 143 } else if order(parentNodeIndex: rightNodeIndex,childNodeIndex: currentNodeIndeX) 144 && order(parentNodeIndex: rightNodeIndex,childNodeIndex: leftNodeIndeX) { 145 // current node has to swapped with the right node 146 swapValuesAt(index1: currentNodeIndex,index2: rightNodeIndeX) 147 currentNodeIndex = rightNodeIndex 148 } else { 149 break 150 } 151 } 152 } 153 154 // Sift up the last node to the correct position until the heap properties are satisfied 155 private func siftUp() { 156 guard !isEmpty else { 157 return 158 } 159 160 var currentNodeIndex = lastNodeIndex 161 while currentNodeIndex > rootNodeIndex { 162 let parentNodeIndex = parent(of: currentNodeIndeX) 163 if order(parentNodeValue: values[parentNodeIndex],childNodeValue: values[currentNodeIndex]) { 164 break 165 } else { 166 swapValuesAt(index1: currentNodeIndex,index2: parentNodeIndeX) 167 currentNodeIndex = parentNodeIndex 168 } 169 } 170 } 171 172 // MARK: Helper methods 173 174 private func swapValuesAt(index1: Int,index2: int) { 175 guard !isEmpty && index1 < count && index2 < count else { 176 return 177 } 178 179 let temp = values[index1] 180 values[index1] = values[index2] 181 values[index2] = temp 182 } 183 184 private func left(of index: int) -> Int { 185 return 2 * index + 1 186 } 187 188 private func right(of index: int) -> Int { 189 return 2 * index + 2 190 } 191 192 private func isValid(index: int) -> Bool { 193 return index >= 0 && index < values.count 194 } 195 196 private func parent(of index: int) -> Int { 197 return Int(ceil(Double(indeX)/2) - 1.0) 198 } 199 200 public func printValues() { 201 log("Heap: \(values)") 202 } 203 204 } 205 206 public class MinHeap<ValueType: Comparable>: Heap<ValueType> { 207 208 public override init(debug: Bool = false) { 209 super.init(debug: debug) 210 } 211 212 override func order(parentNodeValue: ValueType,childNodeValue: ValueTypE) -> Bool { 213 return parentNodeValue <= childNodeValue 214 } 215 216 public func min() -> ValueType? { 217 return rootValue() 218 } 219 } 220 221 public class MaxHeap<ValueType: Comparable>: Heap<ValueType> { 222 223 public override init(debug: Bool = false) { 224 super.init(debug: debug) 225 } 226 227 override func order(parentNodeValue: ValueType,childNodeValue: ValueTypE) -> Bool { 228 return parentNodeValue >= childNodeValue 229 } 230 231 public func max() -> ValueType? { 232 return rootValue() 233 } 234 }
1076ms
1 class KthLargest { 2 var list:[Int] = [Int]() 3 var kth:Int = 0 4 init(_ k: Int,_ nums: [Int]) { 5 var nums = nums 6 nums.sort(by: >) 7 for num in nums { 8 if list.count <= k { 9 list.append(num) 10 } 11 } 12 kth = k 13 } 14 15 func add(_ val: int) -> Int { 16 if list.count == 0 { 17 list.append(val) 18 } else { 19 if val > list.last! { 20 for i in 0 ..< list.count { 21 var temp = list[i] 22 if val >= temp { 23 list.insert(val,at: i) 24 break; 25 } 26 } 27 }else { 28 if list.count < kth { 29 list.append(val) 30 } 31 } 32 if list.count > kth { 33 list.removeLast() 34 } 35 } 36 return list[kth-1] 37 } 38 }
1408ms
1 class KthLargest { 2 3 fileprivate var array :[Int] 4 fileprivate var k :Int 5 6 init(_ k: Int,_ nums: [Int]) { 7 array = nums 8 self.k = k 9 10 if array.count >= k { 11 array.sort(by: >) 12 array = Array(arraY[0...k-1]) 13 } 14 15 } 16 17 func add(_ val: int) -> Int { 18 19 if array.count < k-1 { 20 21 array.append(val) 22 return 0 23 24 }else if array.count == k-1{ 25 26 array.append(val) 27 array = array.sorted(by: >) 28 29 return arraY[k-1] 30 } 31 32 if val >= arraY[0] { 33 34 array.insert(val,at: 0) 35 array.removeLast() 36 37 }else if val < arraY[k-1] { 38 // 空 39 }else { 40 41 for i in 0...k-1 { 42 if arraY[i] <= val { 43 array.insert(val,at: i) 44 array.removeLast() 45 break 46 } 47 } 48 } 49 50 return arraY[k-1] 51 } 52 }
以上是大佬教程为你收集整理的[Swift]LeetCode703. 数据流中的第K大元素 | Kth Largest Element in a Stream全部内容，希望文章能够帮你解决[Swift]LeetCode703. 数据流中的第K大元素 | Kth Largest Element in a Stream所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。