剑指 Offer 41. 数据流中的中位数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

type MinHeap struct {
    sort.IntSlice
}

func (hp *MinHeap) Less(i, j int) bool {
    return hp.IntSlice[i] < hp.IntSlice[j]
}

func (hp *MinHeap) Push(x interface{}) {
    hp.IntSlice = append(hp.IntSlice, x.(int))
}

func (hp *MinHeap) Pop() interface{} {
    ret := hp.IntSlice[len(hp.IntSlice)-1]
    hp.IntSlice = hp.IntSlice[:len(hp.IntSlice)-1]
    return ret
}

type MaxHeap struct {
    sort.IntSlice
}

func (hp *MaxHeap) Less(i, j int) bool {
    return hp.IntSlice[i] > hp.IntSlice[j]
}

func (hp *MaxHeap) Push(x interface{}) {
    hp.IntSlice = append(hp.IntSlice, x.(int))
}

func (hp *MaxHeap) Pop() interface{} {
    ret := hp.IntSlice[len(hp.IntSlice)-1]
    hp.IntSlice = hp.IntSlice[:len(hp.IntSlice)-1]
    return ret
}

type MedianFinder struct {
    minHeap MinHeap
    maxHeap MaxHeap
}

/** initialize your data structure here. */
func Constructor() MedianFinder {
    return MedianFinder{minHeap: MinHeap{}, maxHeap: MaxHeap{}}
}

func (this *MedianFinder) AddNum(num int) {
    minHeap, maxHeap := &this.minHeap, &this.maxHeap
    if len(minHeap.IntSlice) == len(maxHeap.IntSlice) {
        if len(maxHeap.IntSlice) == 0 {
            heap.Push(maxHeap, num)
        } else {
            if num > minHeap.IntSlice[0] {
                heap.Push(maxHeap, heap.Pop(minHeap))
                heap.Push(minHeap, num)
            } else {
                heap.Push(maxHeap, num)
            }
        }
    } else {
        if num > maxHeap.IntSlice[0] {
            heap.Push(minHeap, num)
        } else {
            heap.Push(minHeap, heap.Pop(maxHeap))
            heap.Push(maxHeap, num)
        }
    }
}

func (this *MedianFinder) FindMedian() float64 {
    minHeap, maxHeap := &this.minHeap, &this.maxHeap
    if len(minHeap.IntSlice) == len(maxHeap.IntSlice) {
        return (float64(minHeap.IntSlice[0]) + float64(maxHeap.IntSlice[0])) / 2
    } else {
        return float64(maxHeap.IntSlice[0])
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddNum(num);
 * param_2 := obj.FindMedian();
 */

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

type MinHeap []int

func (s *MinHeap) Less(i, j int) bool { return (*s)[i] < (*s)[j] }
func (s *MinHeap) Swap(i, j int)      { (*s)[i], (*s)[j] = (*s)[j], (*s)[i] }
func (s *MinHeap) Len() int           { return len(*s) }

func (s *MinHeap) Push(x interface{}) {
    *s = append(*s, x.(int))
}
func (s *MinHeap) Pop() interface{} {
    n := len(*s)
    val := (*s)[n-1]
    *s = (*s)[:n-1]
    return val
}

type MaxHeap struct {
    MinHeap
}

func (s *MaxHeap) Less(i, j int) bool {
    return s.MinHeap[i] > s.MinHeap[j]
}

type MedianFinder struct {
    mMinHeap MinHeap
    mMaxHeap MaxHeap
}

/** initialize your data structure here. */
func Constructor() MedianFinder {
    return MedianFinder{}
}

func (this *MedianFinder) AddNum(num int) {
    if len(this.mMinHeap) == len(this.mMaxHeap.MinHeap) {
        heap.Push(&this.mMaxHeap, num)
        heap.Push(&this.mMinHeap, heap.Pop(&this.mMaxHeap))
    } else {
        heap.Push(&this.mMinHeap, num)
        heap.Push(&this.mMaxHeap, heap.Pop(&this.mMinHeap))
    }
}

func (this *MedianFinder) FindMedian() float64 {
    if len(this.mMaxHeap.MinHeap) == len(this.mMinHeap) {
        return float64(this.mMaxHeap.MinHeap[0]+this.mMinHeap[0]) / 2
    } else {
        return float64(this.mMinHeap[0])
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

type MedianFinder struct {
    queMin, queMax hp
}

func Constructor() MedianFinder {
    return MedianFinder{}
}

func (mf *MedianFinder) AddNum(num int) {
    minQ, maxQ := &mf.queMin, &mf.queMax
    if minQ.Len() == 0 || num <= -minQ.IntSlice[0] {
        heap.Push(minQ, -num)
        if maxQ.Len()+1 < minQ.Len() {
            heap.Push(maxQ, -heap.Pop(minQ).(int))
        }
    } else {
        heap.Push(maxQ, num)
        if maxQ.Len() > minQ.Len() {
            heap.Push(minQ, -heap.Pop(maxQ).(int))
        }
    }
}

func (mf *MedianFinder) FindMedian() float64 {
    minQ, maxQ := mf.queMin, mf.queMax
    if minQ.Len() > maxQ.Len() {
        return float64(-minQ.IntSlice[0])
    }
    return float64(maxQ.IntSlice[0]-minQ.IntSlice[0]) / 2
}

type hp struct{ sort.IntSlice }
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{}   { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

type Heap struct {
    sort.IntSlice
}

func (h *Heap) Push(x interface{}) {
    h.IntSlice = append(h.IntSlice, x.(int))
}

func (h *Heap) Pop() interface{} {
    a := h.IntSlice
    ret := a[len(a)-1]
    h.IntSlice = a[:len(a)-1]
    return ret
}

type MedianFinder struct {
    queMin Heap // 存储小于等于中位数的数字
    queMax Heap // 存储大于等于中位数的数字
}

/** initialize your data structure here. */
func Constructor() MedianFinder {
    return MedianFinder{queMin: Heap{}, queMax: Heap{}}
}

func (this *MedianFinder) AddNum(num int) {
    minQ, maxQ := &this.queMin, &this.queMax
    if len(minQ.IntSlice) == len(maxQ.IntSlice) {
        if len(minQ.IntSlice) == 0 {
            heap.Push(minQ, -num)
        } else {
            if num > maxQ.IntSlice[0] {
                heap.Push(minQ, -1*heap.Pop(maxQ).(int))
                heap.Push(maxQ, num)
            } else {
                heap.Push(minQ, -num)
            }
        }
    } else {
        if -num > minQ.IntSlice[0] {
            heap.Push(maxQ, -1*heap.Pop(minQ).(int))
            heap.Push(minQ, -num)
        } else {
            heap.Push(maxQ, num)
        }
    }
}

func (this *MedianFinder) FindMedian() float64 {
    minQ, maxQ := &this.queMin, &this.queMax
    if len(minQ.IntSlice) == len(maxQ.IntSlice) {
        return float64(-minQ.IntSlice[0]+maxQ.IntSlice[0]) / 2
    } else {
        return float64(-minQ.IntSlice[0])
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddNum(num);
 * param_2 := obj.FindMedian();
 */