leetcode46，[Swift]LeetCode480. 滑動窗口中位數 | Sliding Window Median

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
?微信公眾號：山青詠芝（shanqingyongzhi）
?博客園地址：山青詠芝（https://www.cnblogs.com/strengthen/）
?GitHub地址：https://github.com/strengthen/LeetCode
?原文地址：https://www.cnblogs.com/strengthen/p/10805204.html?
?如果鏈接不是山青詠芝的博客園地址，則可能是爬取作者的文章。
?原文已修改更新！強烈建議點擊原文地址閱讀！支持作者！支持原創！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

leetcode46？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       11 [3  -1  -3] 5  3  6  7       -11  3 [-1  -3  5] 3  6  7       -11  3  -1 [-3  5  3] 6  7       31  3  -1  -3 [5  3  6] 7       51  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       11 [3  -1  -3] 5  3  6  7       -11  3 [-1  -3  5] 3  6  7       -11  3  -1 [-3  5  3] 6  7       31  3  -1  -3 [5  3  6] 7       51  3  -1  -3  5 [3  6  7]      6

?因此，返回該滑動窗口的中位數數組?[1,-1,-1,3,5,6]。

提示：
假設k是合法的，即：k?始終小于輸入的非空數組的元素個數.

---

408ms

class Solution {
    func medianSlidingWindow(_ nums: [Int], _ k: Int) -> [Double] {
        guard nums.count >= k else {
            return []
        }
        
        var result = [Double]()
        result.reserveCapacity(nums.count - k + 1)
        var window = nums[0..<k].sorted()
        for i in 0..<(nums.count - k + 1) {
            if i > 0 {
                window.insertOrdered(nums[i - 1 + k])
            }
            result.append(window.median)
            window.remove(nums[i])
        }
        
        return result
    }
}

extension Array where Element == Int {
    var median: Double {
        return (Double(self[(count - 1) / 2]) + Double(self[(count) / 2])) / 2
    }
    
    mutating func insertOrdered(_ val: Int) {
        for i in 0..<count {
            if self[i] > val {
                self.insert(val, at: i)
                return
            }
        }
        append(val)
    }
    
    mutating func remove(_ val: Int) {
        for i in 0..<count {
            if self[i] == val {
                self.remove(at: i)
                return
            }
        }
    }
}

---

Runtime:?492 ms

Memory Usage:?20.3 MB

class Solution {
    func medianSlidingWindow(_ nums: [Int], _ k: Int) -> [Double] {
        var k = k
        var res:[Double] = [Double]()
        var record:[(Int,Int)] = [(Int,Int)]()
        for i in 0..<k
        {
            record.append((nums[i],i))
        }
        record.sort(by: cmp)
        update(&res, &record, &k)
        for i in k..<nums.count
        {
            record.remove(at: beforePos(&record, i - k))
            record.insert((nums[i],i), at: binPos(&record, nums[i]))
            update(&res, &record, &k)
        }
        return res
    }
    
    func cmp(_ a:(Int,Int),_ b:(Int,Int)) -> Bool
    {
        if a.0 == b.0 {return a.1 < b.1}
        return a.0 < b.0
    }
    
    func binPos(_ record:inout [(Int,Int)],_ target:Int) -> Int
    {
        var left:Int = 0
        var right:Int = record.count
        while(left < right)
        {
            let middle:Int = left + (right - left) / 2
            if record[ middle].0 == target
            {
                return middle
            }
            else if record[ middle].0 < target
            {
                left = middle + 1
            }
            else
            {
                right = middle
            }
        }
        return left
    }
    
    func beforePos(_ record:inout [(Int,Int)],_ j:Int) -> Int
    {
        for i in 0..<record.count
        {
            if record[i].1 == j
            {
                return i
            }
        }
        return 0
    }
    
    func update(_ res:inout [Double],_ record:inout [(Int,Int)],_ k:inout Int )
    {
        if k % 2 == 1
        {
            res.append(Double(record[ record.count / 2].0))
        }
        else
        {
            res.append(Double(record[ record.count / 2].0) * 1.0 / 2 + Double(record[ record.count/2-1].0) * 1.0 / 2)
        }
    }
}

---

636ms

class Solution {
    var maxHeap = Heap<Int>(sort: >)
var minHeap = Heap<Int>(sort: <)

func medianSlidingWindow(_ nums: [Int], _ k: Int) -> [Double] {
    var res = [Double]()
    
    for (index, value) in nums.enumerated() {
        if maxHeap.isEmpty || value <= maxHeap.peek()! {
            maxHeap.insert(value)
        } else {
            minHeap.insert(value)
        }
        
        balance()
        
        let removeTarget = index - k
        if removeTarget >= 0 {
            if nums[removeTarget] > maxHeap.peek()! {
                minHeap.remove(node: nums[removeTarget])
            } else {
                maxHeap.remove(node: nums[removeTarget])
            }
        }
        
        balance()
        
        if index >= k - 1 {
            if k % 2 == 0 {
                res.append((Double(minHeap.peek()!) + Double(maxHeap.peek()!)) / 2)
            } else {
                res.append(Double(maxHeap.peek()!))
            }
        }
    }
    
    return res
}

func balance() {
    while maxHeap.count < minHeap.count {
        maxHeap.insert(minHeap.remove()!)
    }
    
    while minHeap.count < maxHeap.count - 1 {
        minHeap.insert(maxHeap.remove()!)
    }
  }
}


// swfit heap:
public struct Heap<T> {
    /** The array that stores the heap's nodes. */
    var nodes = [T]()
    
    /**
     * Determines how to compare two nodes in the heap.
     * Use '>' for a max-heap or '<' for a min-heap,
     * or provide a comparing method if the heap is made
     * of custom elements, for example tuples.
     */
    private var orderCriteria: (T, T) -> Bool
    
    /**
     * Creates an empty heap.
     * The sort function determines whether this is a min-heap or max-heap.
     * For comparable data types, > makes a max-heap, < makes a min-heap.
     */
    public init(sort: @escaping (T, T) -> Bool) {
        orderCriteria = sort
    }
    
    /**
     * Creates a heap from an array. The order of the array does not matter;
     * the elements are inserted into the heap in the order determined by the
     * sort function. For comparable data types, '>' makes a max-heap,
     * '<' makes a min-heap.
     */
    public init(array: [T], sort: @escaping (T, T) -> Bool) {
        orderCriteria = sort
        configureHeap(from: array)
    }
    
    /**
     * Configures the max-heap or min-heap from an array, in a bottom-up manner.
     * Performance: This runs pretty much in O(n).
     */
    private mutating func configureHeap(from array: [T]) {
        nodes = array
        for i in stride(from: (nodes.count / 2 - 1), through: 0, by: -1) {
            shiftDown(i)
        }
    }
    
    public var isEmpty: Bool {
        return nodes.isEmpty
    }
    
    public var count: Int {
        return nodes.count
    }
    
    /**
     * Returns the index of the parent of the element at index i.
     * The element at index 0 is the root of the tree and has no parent.
     */
    @inline(__always) internal func parentIndex(ofIndex i: Int) -> Int {
        return (i - 1) / 2
    }
    
    /**
     * Returns the index of the left child of the element at index i.
     * Note that this index can be greater than the heap size, in which case
     * there is no left child.
     */
    @inline(__always) internal func leftChildIndex(ofIndex i: Int) -> Int {
        return 2 * i + 1
    }
    
    /**
     * Returns the index of the right child of the element at index i.
     * Note that this index can be greater than the heap size, in which case
     * there is no right child.
     */
    @inline(__always) internal func rightChildIndex(ofIndex i: Int) -> Int {
        return 2 * i + 2
    }
    
    /**
     * Returns the maximum value in the heap (for a max-heap) or the minimum
     * value (for a min-heap).
     */
    public func peek() -> T? {
        return nodes.first
    }
    
    /**
     * Adds a new value to the heap. This reorders the heap so that the max-heap
     * or min-heap property still holds. Performance: O(log n).
     */
    public mutating func insert(_ value: T) {
        nodes.append(value)
        shiftUp(nodes.count - 1)
    }
    
    /**
     * Adds a sequence of values to the heap. This reorders the heap so that
     * the max-heap or min-heap property still holds. Performance: O(log n).
     */
    public mutating func insert<S: Sequence>(_ sequence: S) where S.Iterator.Element == T {
        for value in sequence {
            insert(value)
        }
    }
    
    /**
     * Allows you to change an element. This reorders the heap so that
     * the max-heap or min-heap property still holds.
     */
    public mutating func replace(index i: Int, value: T) {
        guard i < nodes.count else { return }
        
        remove(at: i)
        insert(value)
    }
    
    /**
     * Removes the root node from the heap. For a max-heap, this is the maximum
     * value; for a min-heap it is the minimum value. Performance: O(log n).
     */
    @discardableResult public mutating func remove() -> T? {
        guard !nodes.isEmpty else { return nil }
        
        if nodes.count == 1 {
            return nodes.removeLast()
        } else {
            // Use the last node to replace the first one, then fix the heap by
            // shifting this new first node into its proper position.
            let value = nodes[0]
            nodes[0] = nodes.removeLast()
            shiftDown(0)
            return value
        }
    }
    
    /**
     * Removes an arbitrary node from the heap. Performance: O(log n).
     * Note that you need to know the node's index.
     */
    @discardableResult public mutating func remove(at index: Int) -> T? {
        guard index < nodes.count else { return nil }
        
        let size = nodes.count - 1
        if index != size {
            nodes.swapAt(index, size)
            shiftDown(from: index, until: size)
            shiftUp(index)
        }
        return nodes.removeLast()
    }
    
    /**
     * Takes a child node and looks at its parents; if a parent is not larger
     * (max-heap) or not smaller (min-heap) than the child, we exchange them.
     */
    internal mutating func shiftUp(_ index: Int) {
        var childIndex = index
        let child = nodes[childIndex]
        var parentIndex = self.parentIndex(ofIndex: childIndex)
        
        while childIndex > 0 && orderCriteria(child, nodes[parentIndex]) {
            nodes[childIndex] = nodes[parentIndex]
            childIndex = parentIndex
            parentIndex = self.parentIndex(ofIndex: childIndex)
        }
        
        nodes[childIndex] = child
    }
    
    /**
     * Looks at a parent node and makes sure it is still larger (max-heap) or
     * smaller (min-heap) than its childeren.
     */
    internal mutating func shiftDown(from index: Int, until endIndex: Int) {
        let leftChildIndex = self.leftChildIndex(ofIndex: index)
        let rightChildIndex = leftChildIndex + 1
        
        // Figure out which comes first if we order them by the sort function:
        // the parent, the left child, or the right child. If the parent comes
        // first, we're done. If not, that element is out-of-place and we make
        // it "float down" the tree until the heap property is restored.
        var first = index
        if leftChildIndex < endIndex && orderCriteria(nodes[leftChildIndex], nodes[first]) {
            first = leftChildIndex
        }
        if rightChildIndex < endIndex && orderCriteria(nodes[rightChildIndex], nodes[first]) {
            first = rightChildIndex
        }
        if first == index { return }
        
        nodes.swapAt(index, first)
        shiftDown(from: first, until: endIndex)
    }
    
    internal mutating func shiftDown(_ index: Int) {
        shiftDown(from: index, until: nodes.count)
    }
}

// MARK: - Searching

extension Heap where T: Equatable {
    /** Get the index of a node in the heap. Performance: O(n). */
    public func index(of node: T) -> Int? {
        return nodes.index(where: { $0 == node })
    }
    
    /** Removes the first occurrence of a node from the heap. Performance: O(n log n). */
    @discardableResult public mutating func remove(node: T) -> T? {
        if let index = index(of: node) {
            return remove(at: index)
        }
        return nil
    }
}

?

?