[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 whi

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 4kthLargest.add(5);   // returns 5kthLargest.add(10);  // returns 5kthLargest.add(9);   // returns 8kthLargest.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 4kthLargest.add(5);   // returns 5kthLargest.add(10);  // returns 5kthLargest.add(9);   // returns 8kthLargest.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 - k14         while temp > 0 {15             self.queue.dequeue()16             temp -= 117         }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.first34     }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 = 049         var slindex = 050         var sRIndex = 051         var index = 052         53         while pIndex * 2 + 1 <= array.count - 1  {54             slindex = pIndex * 2 + 155             sRIndex = pIndex * 2 + 256             index = pIndex57             58             if array[pIndex] > array[slindex] {59                 index = slindex60             }61             62             if sRIndex <= array.count - 1 && array[index] > array[sRIndex] {63                 index = sRIndex64             }65             66             if (pIndex != index) {67                 array.swapAt(pIndex,index)68                 pIndex = index69             } else {70                 return71             }72         }73     }74     75     mutating func siftUp() {76         var pIndex = 077         var sIndex = array.count - 178         79         while sIndex != 0 {80             pIndex = (sIndex - 1) / 281             if (array[sIndex] < array[pIndex]) {82                 array.swapAt(sIndex,pIndex)83                 sIndex = pIndex84             } else {85                 return86             }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 = 0101         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 = smallerChildindex110             }else{111                 break112             }113         }114     }115     116     var count:Int{117         return self.data.count118     }119 }

Runtime: 208 ms Memory Usage: 20.1 MB

  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) + 1100     }101     102     func rightIndex(of index: Int) -> Int {103         return (2 * index) + 2104     }105     106     func parentIndex(of index: Int) -> Int {107         return (index - 1) / 2108     }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) / 2103     }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 startIndex110         } else if element > elements[startIndex] {111             return nil // can‘t be in heap112         } else if let foundindex = firstIndex(of: element,startingAt: leftChildindex(for: startIndex)) {113             return foundindex // need to check both left and right children114         } else if let foundindex = firstIndex(of: element,startingAt: rightChildindex(for: startIndex)) {115             return foundindex // need to check both left and right children116         }117 118         return nil // element was smaller than any element in the heap119     }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 = parentIndex134 135         let leftChildindex = self.leftChildindex(for: parentIndex)136         if leftChildindex < elements.count && areInIncreasingOrder(elements[leftChildindex],elements[maxElementIndex]) {137             maxElementIndex = leftChildindex138         }139 140         let rightChildindex = self.rightChildindex(for: parentIndex)141         if rightChildindex < elements.count && areInIncreasingOrder(elements[rightChildindex],elements[maxElementIndex]) {142             maxElementIndex = rightChildindex143         }144 145         if parentIndex == maxElementIndex {146             return // base case147         } 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 = 013         var right = nums.count - 114         // [2,4,8]15         while left <= right {16             var mID = (left + right + 1) / 217             if nums[mID] == val {18                 left = mID19                 right = mID - 120             } else if nums[mID] > val {21                 right = mID - 122             } else {23                 left = mID + 124             }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 Methods107     private func heAPIfy(_ i: Int) {108         var top = i109         110         if let left = left(i),type.compare(heap[left],heap[top]) {111             top = left112         }113         114         if let right = right(i),type.compare(heap[right],heap[top]) {115             top = right116         }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 = i127         128         while let p = parent,type.compare(heap[this],heap[p]) {129             heap.swapAt(p,this)130             parent = parentIndex(p)131             this = p132         }133     }134     135     private func parentIndex(_ i: Int) -> Int? {136         guard i > 0 else { return nil }137         return (i - 1) / 2138     }139     140     private func left(_ i: Int) -> Int? {141         let left = i * 2 + 1142         return left < heap.count ? left : nil143     }144     145     private func right(_ i: Int) -> Int? {146         let right = i * 2 + 2147         return right < heap.count ? right : nil148     }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     // Remove102     // Swap -> Sift Down( compare with two children)103     mutating func remove() -> Element? {104         guard !isEmpty else {105             return nil106         }107         elements.swapAt(0,count - 1)108         defer {109             siftDown(from: 0)110         }111         return elements.removeLast()112     }113     114     // Insert115     // Append -> sift(guolv) up116     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 nil124         }125         if sort(element,elements[i]) {126             return nil127         }128         if element == elements[i] {129             return i130         }131         if let j = index(of: element,startingAt: leftChildindex(ofParentAt: i)) {132             return j133         }134         if let j = index(of: element,startingAt: rightChildindex(ofParentAt: i)) {135             return j136         }137         return nil138     }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 = p132         }133     }134     135     private func parentIndex(_ i: Int) -> Int? {136         guard i > 0 else { return nil }137         return (i - 1) / 2138     }139     140     private func left(_ i: Int) -> Int? {141         let left = i * 2 + 1142         return left < heap.count ? left : nil143     }144     145     private func right(_ i: Int) -> Int? {146         let right = i * 2 + 2147         return right < heap.count ? right : nil148     }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 nil101         }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 rootValue110     }111 112     // Constant time113     public func rootValue() -> ValueType? {114         guard !isEmpty else {115             return nil116         }117 118         return values[rootNodeIndex]119     }120 121     // MARK: Private methods122 123     // Sift down the root node to the correct position until the heap propertIEs are satisfIEd124     private func siftDown() {125         guard !isEmpty else {126             return127         }128 129         var currentNodeIndex = rootNodeIndex130         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 position137                     break138             } else if order(parentNodeIndex: leftNodeIndex,childNodeIndex: currentNodeIndex)139                 && order(parentNodeIndex: leftNodeIndex,childNodeIndex: rightNodeIndex) {140                     // current node has to swapped with the left node141                     swapValuesAt(index1: currentNodeIndex,index2: leftNodeIndex)142                     currentNodeIndex = leftNodeIndex143             } else if order(parentNodeIndex: rightNodeIndex,childNodeIndex: currentNodeIndex)144                 && order(parentNodeIndex: rightNodeIndex,childNodeIndex: leftNodeIndex) {145                     // current node has to swapped with the right node146                     swapValuesAt(index1: currentNodeIndex,index2: rightNodeIndex)147                     currentNodeIndex = rightNodeIndex148             } else {149                     break150             }151         }152     }153 154     // Sift up the last node to the correct position until the heap propertIEs are satisfIEd155     private func siftUp() {156         guard !isEmpty else {157             return158         }159 160         var currentNodeIndex = lastNodeIndex161         while currentNodeIndex > rootNodeIndex {162             let parentNodeIndex = parent(of: currentNodeIndex)163             if order(parentNodeValue: values[parentNodeIndex],childNodeValue: values[currentNodeIndex]) {164                 break165             } else {166                 swapValuesAt(index1: currentNodeIndex,index2: parentNodeIndex)167                 currentNodeIndex = parentNodeIndex168             }169         }170     }171 172     // MARK: Helper methods173 174     private func swapValuesAt(index1: Int,index2: Int) {175         guard !isEmpty && index1 < count && index2 < count else {176             return177         }178 179         let temp = values[index1]180         values[index1] = values[index2]181         values[index2] = temp182     }183 184     private func left(of index: Int) -> Int {185         return 2 * index + 1186     }187 188     private func right(of index: Int) -> Int {189         return 2 * index + 2190     }191 192     private func isValID(index: Int) -> Bool {193         return index >= 0 && index < values.count194     }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 <= childNodeValue214     }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 >= childNodeValue229     }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 = k13     }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 023             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                     break46                 }47             }48         }49         50         return array[k-1]51     }52 }

@H_403_5397@ 总结

以上是内存溢出为你收集整理的[Swift]LeetCode703. 数据流中的第K大元素 | Kth Largest Element in a Stream全部内容，希望文章能够帮你解决[Swift]LeetCode703. 数据流中的第K大元素 | Kth Largest Element in a Stream所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。