• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode480.滑动窗口中位数|SlidingWindowMedian

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples: 

[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Median
---------------               -----
[1  3  -1] -3  5  3  6  7       1
 1 [3  -1  -3] 5  3  6  7       -1
 1  3 [-1  -3  5] 3  6  7       -1
 1  3  -1 [-3  5  3] 6  7       3
 1  3  -1  -3 [5  3  6] 7       5
 1  3  -1  -3  5 [3  6  7]      6

Therefore, return the median sliding window as [1,-1,-1,3,5,6].

Note: 
You may assume k is always valid, ie: k is always smaller than input array's size for non-empty array.


中位数是有序序列最中间的那个数。如果序列的大小是偶数,则没有最中间的数;此时中位数是最中间的两个数的平均数。

例如:

[2,3,4],中位数是 3

[2,3],中位数是 (2 + 3) / 2 = 2.5

给出一个数组 nums,有一个大小为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数,每次窗口移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数,并输出由它们组成的数组。

例如:

给出 nums = [1,3,-1,-3,5,3,6,7],以及 k = 3。

窗口位置                      中位数
---------------               -----
[1  3  -1] -3  5  3  6  7       1
 1 [3  -1  -3] 5  3  6  7       -1
 1  3 [-1  -3  5] 3  6  7       -1
 1  3  -1 [-3  5  3] 6  7       3
 1  3  -1  -3 [5  3  6] 7       5
 1  3  -1  -3  5 [3  6  7]      6

 因此,返回该滑动窗口的中位数数组 [1,-1,-1,3,5,6]

提示:
假设k是合法的,即:k 始终小于输入的非空数组的元素个数.


408ms

 1 class Solution {
 2     func medianSlidingWindow(_ nums: [Int], _ k: Int) -> [Double] {
 3         guard nums.count >= k else {
 4             return []
 5         }
 6         
 7         var result = [Double]()
 8         result.reserveCapacity(nums.count - k + 1)
 9         var window = nums[0..<k].sorted()
10         for i in 0..<(nums.count - k + 1) {
11             if i > 0 {
12                 window.insertOrdered(nums[i - 1 + k])
13             }
14             result.append(window.median)
15             window.remove(nums[i])
16         }
17         
18         return result
19     }
20 }
21 
22 extension Array where Element == Int {
23     var median: Double {
24         return (Double(self[(count - 1) / 2]) + Double(self[(count) / 2])) / 2
25     }
26     
27     mutating func insertOrdered(_ val: Int) {
28         for i in 0..<count {
29             if self[i] > val {
30                 self.insert(val, at: i)
31                 return
32             }
33         }
34         append(val)
35     }
36     
37     mutating func remove(_ val: Int) {
38         for i in 0..<count {
39             if self[i] == val {
40                 self.remove(at: i)
41                 return
42             }
43         }
44     }
45 }

Runtime: 492 ms
Memory Usage: 20.3 MB
 1 class Solution {
 2     func medianSlidingWindow(_ nums: [Int], _ k: Int) -> [Double] {
 3         var k = k
 4         var res:[Double] = [Double]()
 5         var record:[(Int,Int)] = [(Int,Int)]()
 6         for i in 0..<k
 7         {
 8             record.append((nums[i],i))
 9         }
10         record.sort(by: cmp)
11         update(&res, &record, &k)
12         for i in k..<nums.count
13         {
14             record.remove(at: beforePos(&record, i - k))
15             record.insert((nums[i],i), at: binPos(&record, nums[i]))
16             update(&res, &record, &k)
17         }
18         return res
19     }
20     
21     func cmp(_ a:(Int,Int),_ b:(Int,Int)) -> Bool
22     {
23         if a.0 == b.0 {return a.1 < b.1}
24         return a.0 < b.0
25     }
26     
27     func binPos(_ record:inout [(Int,Int)],_ target:Int) -> Int
28     {
29         var left:Int = 0
30         var right:Int = record.count
31         while(left < right)
32         {
33             let middle:Int = left + (right - left) / 2
34             if record[ middle].0 == target
35             {
36                 return middle
37             }
38             else if record[ middle].0 < target
39             {
40                 left = middle + 1
41             }
42             else
43             {
44                 right = middle
45             }
46         }
47         return left
48     }
49     
50     func beforePos(_ record:inout [(Int,Int)],_ j:Int) -> Int
51     {
52         for i in 0..<record.count
53         {
54             if record[i].1 == j
55             {
56                 return i
57             }
58         }
59         return 0
60     }
61     
62     func update(_ res:inout [Double],_ record:inout [(Int,Int)],_ k:inout Int )
63     {
64         if k % 2 == 1
65         {
66             res.append(Double(record[ record.count / 2].0))
67         }
68         else
69         {
70             res.append(Double(record[ record.count / 2].0) * 1.0 / 2 + Double(record[ record.count/2-1].0) * 1.0 / 2)
71         }
72     }
73 }

636ms

  1 class Solution {
  2     var maxHeap = Heap<Int>(sort: >)
  3 var minHeap = Heap<Int>(sort: <)
  4 
  5 func medianSlidingWindow(_ nums: [Int], _ k: Int) -> [Double] {
  6     var res = [Double]()
  7     
  8     for (index, value) in nums.enumerated() {
  9         if maxHeap.isEmpty || value <= maxHeap.peek()! {
 10             maxHeap.insert(value)
 11         } else {
 12             minHeap.insert(value)
 13         }
 14         
 15         balance()
 16         
 17         let removeTarget = index - k
 18         if removeTarget >= 0 {
 19             if nums[removeTarget] > maxHeap.peek()! {
 20                 minHeap.remove(node: nums[removeTarget])
 21             } else {
 22                 maxHeap.remove(node: nums[removeTarget])
 23             }
 24         }
 25         
 26         balance()
 27         
 28         if index >= k - 1 {
 29             if k % 2 == 0 {
 30                 res.append((Double(minHeap.peek()!) + Double(maxHeap.peek()!)) / 2)
 31             } else {
 32                 res.append(Double(maxHeap.peek()!))
 33             }
 34         }
 35     }
 36     
 37     return res
 38 }
 39 
 40 func balance() {
 41     while maxHeap.count < minHeap.count {
 42         maxHeap.insert(minHeap.remove()!)
 43     }
 44     
 45     while minHeap.count < maxHeap.count - 1 {
 46         minHeap.insert(maxHeap.remove()!)
 47     }
 48   }
 49 }
 50 
 51 
 52 ////// swfit heap:
 53 public struct Heap<T> {
 54     /** The array that stores the heap's nodes. */
 55     var nodes = [T]()
 56     
 57     /**
 58      * Determines how to compare two nodes in the heap.
 59      * Use '>' for a max-heap or '<' for a min-heap,
 60      * or provide a comparing method if the heap is made
 61      * of custom elements, for example tuples.
 62      */
 63     private var orderCriteria: (T, T) -> Bool
 64     
 65     /**
 66      * Creates an empty heap.
 67      * The sort function determines whether this is a min-heap or max-heap.
 68      * For comparable data types, > makes a max-heap, < makes a min-heap.
 69      */
 70     public init(sort: @escaping (T, T) -> Bool) {
 71         orderCriteria = sort
 72     }
 73     
 74     /**
 75      * Creates a heap from an array. The order of the array does not matter;
 76      * the elements are inserted into the heap in the order determined by the
 77      * sort function. For comparable data types, '>' makes a max-heap,
 78      * '<' makes a min-heap.
 79      */
 80     public init(array: [T], sort: @escaping (T, T) -> Bool) {
 81         orderCriteria = sort
 82         configureHeap(from: array)
 83     }
 84     
 85     /**
 86      * Configures the max-heap or min-heap from an array, in a bottom-up manner.
 87      * Performance: This runs pretty much in O(n).
 88      */
 89     private mutating func configureHeap(from array: [T]) {
 90         nodes = array
 91         for i in stride(from: (nodes.count / 2 - 1), through: 0, by: -1) {
 92             shiftDown(i)
 93         }
 94     }
 95     
 96     public var isEmpty: Bool {
 97         return nodes.isEmpty
 98     }
 99     
100     public var count: Int {
101         return nodes.count
102     }
103     
104     /**
105      * Returns the index of the parent of the element at index i.
106      * The element at index 0 is the root of the tree and has no parent.
107      */
108     @inline(__always) internal func parentIndex(ofIndex i: Int) -> Int {
109         return (i - 1) / 2
110     }
111     
112     /**
113      * Returns the index of the left child of the element at index i.
114      * Note that this index can be greater than the heap size, in which case
115      * there is no left child.
116      */
117     @inline(__always) internal func leftChildIndex(ofIndex i: Int) -> Int {
118         return 2 * i + 1
119     }
120     
121     /**
122      * Returns the index of the right child of the element at index i.
123      * Note that this index can be greater than the heap size, in which case
124      * there is no right child.
125      */
126     @inline(__always) internal func rightChildIndex(ofIndex i: Int) -> Int {
127         return 2 * i + 2
128     }
129     
130     /**
131      * Returns the maximum value in the heap (for a max-heap) or the minimum
132      * value (for a min-heap).
133      */
134     public func peek() -> T? {
135         return nodes.first
136     }
137     
138     /**
139      * Adds a new value to the heap. This reorders the heap so that the max-heap
140      * or min-heap property still holds. Performance: O(log n).
141      */
142     public mutating func insert(_ value: T) {
143         nodes.append(value)
144         shiftUp(nodes.count - 1)
145     }
146     
147     /**
148      * Adds a sequence of values to the heap. This reorders the heap so that
149      * the max-heap or min-heap property still holds. Performance: O(log n).
150      */
151     public mutating func insert<S: Sequence>(_ sequence: S) where S.Iterator.Element == T {
152         for value in sequence {
153             insert(value)
154         }
155     }
156     
157     /**
158      * Allows you to change an element. This reorders the heap so that
159      * the max-heap or min-heap property still holds.
160      */
161     public mutating func replace(index i: Int, value: T) {
162         guard i < nodes.count else { return }
163         
164         remove(at: i)
165         insert(value)
166     }
167     
168     /**
169      * Removes the root node from the heap. For a max-heap, this is the maximum
170      * value; for a min-heap it is the minimum value. Performance: O(log n).
171      */
172     @discardableResult public mutating func remove() -> T? {
173         guard !nodes.isEmpty else { return nil }
174         
175         if nodes.count == 1 {
176             return nodes.removeLast()
177         } else {
178             // Use the last node to replace the first one, then fix the heap by
179             // shifting this new first node into its proper position.
180             let value = nodes[0]
181             nodes[0] = nodes.removeLast()
182             shiftDown(0)
183             return value
184         }
185     }
186     
187     /**
188      * Removes an arbitrary node from the heap. Performance: O(log n).
189      * Note that you need to know the node's index.
190      */
191     @discardableResult public mutating func remove(at index: Int) -> T? {
192         guard index < nodes.count else { return nil }
193         
194         let size = nodes.count - 1
195         if index != size {
196             nodes.swapAt(index, size)
197             shiftDown(from: index, until: size)
198             shiftUp(index)
199         }
200         return nodes.removeLast()
201     }
202     
203     /**
204      * Takes a child node and looks at its parents; if a parent is not larger
205      * (max-heap) or not smaller (min-heap) than the child, we exchange them.
206      */
207     internal mutating func shiftUp(_ index: Int) {
208         var childIndex = index
209         let child = nodes[childIndex]
210         var parentIndex = self.parentIndex(ofIndex: childIndex)
211         
212         while childIndex > 0 && orderCriteria(child, nodes[parentIndex]) {
213             nodes[childIndex] = nodes[parentIndex]
214             childIndex = parentIndex
215             parentIndex = self.parentIndex(ofIndex: childIndex)
216         }
217         
218         nodes[childIndex] = child
219     }
220     
221     /**
222      * Looks at a parent node and makes sure it is still larger (max-heap) or
223      * smaller (min-heap) than its childeren.
224      */
225     internal mutating func shiftDown(from index: Int, until endIndex: Int) {
226         let leftChildIndex = self.leftChildIndex(ofIndex: index)
227         let rightChildIndex = leftChildIndex + 1
228         
229         // Figure out which comes first if we order them by the sort function:
230         // the parent, the left child, or the right child. If the parent comes
231         // first, we're done. If not, that element is out-of-place and we make
232         // it "float down" the tree until the heap property is restored.
233         var first = index
234         if leftChildIndex < endIndex && orderCriteria(nodes[leftChildIndex], nodes[first]) {
235             first = leftChildIndex
236         }
237         if rightChildIndex < endIndex && orderCriteria(nodes[rightChildIndex], nodes[first]) {
238             first = rightChildIndex
239         }
240         if first == index { return }
241         
242         nodes.swapAt(index, first)
243         shiftDown(from: first, until: endIndex)
244     }
245     
246     internal mutating func shiftDown(_ index: Int) {
247         shiftDown(from: index, until: nodes.count)
248     }
249 }
250 
251 // MARK: - Searching
252 
253 extension Heap where T: Equatable {
254     /** Get the index of a node in the heap. Performance: O(n). */
255     public func index(of node: T) -> Int? {
256         return nodes.index(where: { $0 == node })
257     }
258     
259     /** Removes the first occurrence of a node from the heap. Performance: O(n log n). */
260     @discardableResult public mutating func remove(node: T) -> T? {
261         if let index = index(of: node) {
262             return remove(at: index)
263         }
264         return nil
265     }
266 }

 

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift项目中添加main方法发布时间:2022-07-13
下一篇:
使用Swift从头开始创建iOS:探索iOS SDK发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap