480. Sliding Window Median #

题目 #

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 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。

解题思路 #

给定一个数组和一个窗口为 K 的窗口，当窗口从数组的左边滑动到数组右边的时候，输出每次移动窗口以后，在窗口内的排序之后中间大小的值。
这一题是第 239 题的升级版。
这道题最暴力的方法就是将窗口内的元素都排序，时间复杂度 O(n * K)。
另一种思路是用两个优先队列，大顶堆里面的元素都比小顶堆里面的元素小。小顶堆里面存储排序以后中间靠后的值大的元素，大顶堆里面存储排序以后中间靠前的值小的元素。如果 k 是偶数，那么两个堆都有 k/2 个元素，中间值就是两个堆顶的元素；如果 k 是奇数，那么小顶堆比大顶堆多一个元素，中间值就是小顶堆的堆顶元素。删除一个元素，元素都标记到删除的堆中，取 top 的时候注意需要取出没有删除的元素。时间复杂度 O(n * log k) 空间复杂度 O(k)

代码 #


package leetcode

import (
	"container/heap"
	"container/list"
	"sort"
)

// 解法一 用链表按照题意实现 时间复杂度 O(n * k) 空间复杂度 O(k)
func medianSlidingWindow(nums []int, k int) []float64 {
	var res []float64
	w := getWindowList(nums[:k], k)
	res = append(res, getMedian(w, k))

	for p1 := k; p1 < len(nums); p1++ {
		w = removeFromWindow(w, nums[p1-k])
		w = insertInWindow(w, nums[p1])
		res = append(res, getMedian(w, k))
	}
	return res
}

func getWindowList(nums []int, k int) *list.List {
	s := make([]int, k)
	copy(s, nums)
	sort.Ints(s)
	l := list.New()
	for _, n := range s {
		l.PushBack(n)
	}
	return l
}

func removeFromWindow(w *list.List, n int) *list.List {
	for e := w.Front(); e != nil; e = e.Next() {
		if e.Value.(int) == n {
			w.Remove(e)
			return w
		}
	}
	return w
}

func insertInWindow(w *list.List, n int) *list.List {
	for e := w.Front(); e != nil; e = e.Next() {
		if e.Value.(int) >= n {
			w.InsertBefore(n, e)
			return w
		}
	}
	w.PushBack(n)
	return w
}

func getMedian(w *list.List, k int) float64 {
	e := w.Front()
	for i := 0; i < k/2; e, i = e.Next(), i+1 {
	}
	if k%2 == 1 {
		return float64(e.Value.(int))
	}
	p := e.Prev()
	return (float64(e.Value.(int)) + float64(p.Value.(int))) / 2
}

// 解法二 用两个堆实现 时间复杂度 O(n * log k) 空间复杂度 O(k)
// 用两个堆记录窗口内的值
// 大顶堆里面的元素都比小顶堆里面的元素小
// 如果 k 是偶数，那么两个堆都有 k/2 个元素，中间值就是两个堆顶的元素
// 如果 k 是奇数，那么小顶堆比大顶堆多一个元素，中间值就是小顶堆的堆顶元素
// 删除一个元素，元素都标记到删除的堆中，取 top 的时候注意需要取出没有删除的元素
func medianSlidingWindow1(nums []int, k int) []float64 {
	ans := []float64{}
	minH := MinHeapR{}
	maxH := MaxHeapR{}
	if minH.Len() > maxH.Len()+1 {
		maxH.Push(minH.Pop())
	} else if minH.Len() < maxH.Len() {
		minH.Push(maxH.Pop())
	}
	for i := range nums {
		if minH.Len() == 0 || nums[i] >= minH.Top() {
			minH.Push(nums[i])
		} else {
			maxH.Push(nums[i])
		}
		if i >= k {
			if nums[i-k] >= minH.Top() {
				minH.Remove(nums[i-k])
			} else {
				maxH.Remove(nums[i-k])
			}
		}
		if minH.Len() > maxH.Len()+1 {
			maxH.Push(minH.Pop())
		} else if minH.Len() < maxH.Len() {
			minH.Push(maxH.Pop())
		}
		if minH.Len()+maxH.Len() == k {
			if k%2 == 0 {
				ans = append(ans, float64(minH.Top()+maxH.Top())/2.0)
			} else {
				ans = append(ans, float64(minH.Top()))
			}
		}
		// fmt.Printf("%+v, %+v\n", minH, maxH)
	}
	return ans
}

// IntHeap define
type IntHeap struct {
	data []int
}

// Len define
func (h IntHeap) Len() int { return len(h.data) }

// Swap define
func (h IntHeap) Swap(i, j int) { h.data[i], h.data[j] = h.data[j], h.data[i] }

// Push define
func (h *IntHeap) Push(x interface{}) { h.data = append(h.data, x.(int)) }

// Pop define
func (h *IntHeap) Pop() interface{} {
	x := h.data[h.Len()-1]
	h.data = h.data[0 : h.Len()-1]
	return x
}

// Top defines
func (h IntHeap) Top() int {
	return h.data[0]
}

// MinHeap define
type MinHeap struct {
	IntHeap
}

// Less define
func (h MinHeap) Less(i, j int) bool { return h.data[i] < h.data[j] }

// MaxHeap define
type MaxHeap struct {
	IntHeap
}

// Less define
func (h MaxHeap) Less(i, j int) bool { return h.data[i] > h.data[j] }

// MinHeapR define
type MinHeapR struct {
	hp, hpDel MinHeap
}

// Len define
func (h MinHeapR) Len() int { return h.hp.Len() - h.hpDel.Len() }

// Top define
func (h *MinHeapR) Top() int {
	for h.hpDel.Len() > 0 && h.hp.Top() == h.hpDel.Top() {
		heap.Pop(&h.hp)
		heap.Pop(&h.hpDel)
	}
	return h.hp.Top()
}

// Pop define
func (h *MinHeapR) Pop() int {
	x := h.Top()
	heap.Pop(&h.hp)
	return x
}

// Push define
func (h *MinHeapR) Push(x int) { heap.Push(&h.hp, x) }

// Remove define
func (h *MinHeapR) Remove(x int) { heap.Push(&h.hpDel, x) }

// MaxHeapR define
type MaxHeapR struct {
	hp, hpDel MaxHeap
}

// Len define
func (h MaxHeapR) Len() int { return h.hp.Len() - h.hpDel.Len() }

// Top define
func (h *MaxHeapR) Top() int {
	for h.hpDel.Len() > 0 && h.hp.Top() == h.hpDel.Top() {
		heap.Pop(&h.hp)
		heap.Pop(&h.hpDel)
	}
	return h.hp.Top()
}

// Pop define
func (h *MaxHeapR) Pop() int {
	x := h.Top()
	heap.Pop(&h.hp)
	return x
}

// Push define
func (h *MaxHeapR) Push(x int) { heap.Push(&h.hp, x) }

// Remove define
func (h *MaxHeapR) Remove(x int) { heap.Push(&h.hpDel, x) }

⬅️上一页

下一页➡️