[Swift]LeetCode703. 数据流中的第K大元素 | Kth Largest Elemen

发布时间：2020-12-14 04:58:18 所属栏目：百科来源：网络整理

导读：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 integ

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 }

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) + 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 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!