FilesExpand file tree

 master

/

Data Stream Median.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

executable file

·

151 lines (123 loc) · 4.3 KB

 master

/

Data Stream Median.java

Copy path

Top

File metadata and controls

• Code
• Blame

executable file

·

151 lines (123 loc) · 4.3 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

H

1520749166

tags: Heap, Design

#### 原理

- 把Input stream想成向上的山坡. 山坡中间那点，自然就是median.

- 前半段，作为maxHeap,关注点是PriorityQueue的峰点，也就是实际上的median.

- 后半段，作为minHeap,正常的PriorityQueue。 开头是最小的。

#### 注意

- 这里要首先定好, 哪一个queue是多存一个element的. 这里选maxHeap: maxHeap.size() == minHeap.size() + 1 || minHeap.size()

- 必须先维护maxHeap里面有个元素, 否则null了会在比较大小时出问题.

```

/*

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

Design a data structure that supports the following two operations:

void addNum(int num) - Add a integer number from the data stream to the data structure.

double findMedian() - Return the median of all elements so far.

For example:

addNum(1)

addNum(2)

findMedian() -> 1.5

addNum(3)

findMedian() -> 2

*/

/*

Thoughts:

Median value needs to be maintained as we add new items into the structure.

MinHeap, MaxHeap. Maintain it during add.

*/

class MedianFinder {

PriorityQueue<Integer> minHeap;// later

PriorityQueue<Integer> maxHeap;// former

/** initialize your data structure here. */

public MedianFinder() {

minHeap = new PriorityQueue<Integer>();

maxHeap = new PriorityQueue<Integer>(10, Collections.reverseOrder());

}

public void addNum(int num) {

// maxHeap.size() = minHeap.size() + 1

if (maxHeap.isEmpty()) {

maxHeap.add(num);

return;

}

int currMedian = maxHeap.peek();

if (num <= currMedian) {

maxHeap.offer(num);

} else {

minHeap.offer(num);

}

// make sure: maxHeap.size() = minHeap.size() + 1

if (maxHeap.size() > minHeap.size() + 1) {

minHeap.offer(maxHeap.poll());

} else if (maxHeap.size() < minHeap.size()) {

maxHeap.offer(minHeap.poll());

}

}

public double findMedian() {

if (minHeap.size() == maxHeap.size()) {

return (minHeap.peek() + maxHeap.peek()) / 2.0;

} else {

return maxHeap.peek();

}

}

}

/**

* Your MedianFinder object will be instantiated and called as such:

* MedianFinder obj = new MedianFinder();

* obj.addNum(num);

* double param_2 = obj.findMedian();

*/

/*

Numbers keep coming, return the median of numbers at every time a new number added.

Example

For numbers coming list: [1, 2, 3, 4, 5], return [1, 1, 2, 2, 3].

For numbers coming list: [4, 5, 1, 3, 2, 6, 0], return [4, 4, 4, 3, 3, 3, 3].

For numbers coming list: [2, 20, 100], return [2, 2, 20].

Challenge

Total run time in O(nlogn).

Clarification

What's the definition of Median? - Median is the number that in the middle of a sorted array.

If there are n numbers in a sorted array A, the median is A[(n - 1) / 2].

For example, if A=[1,2,3], median is 2. If A=[1,19], median is 1.

Tags Expand

LintCode Copyright Heap Priority Queue

*/

public class Solution {

/**

* @param nums: A list of integers.

* @return: the median of numbers

*/

public int[] medianII(int[] nums) {

int[] rst = new int[nums.length];

if (nums == null || nums.length == 0) {

return rst;

}

PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();

PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(10, new Comparator<Integer>() {

public int compare(Integer x, Integer y) {

return y - x;

}

});

rst[0] = nums[0];

maxHeap.offer(rst[0]);

for (int i = 1; i < rst.length; i++){

int preMedian = maxHeap.peek();

if (nums[i] > preMedian) {

minHeap.offer(nums[i]);

} else {

maxHeap.offer(nums[i]);

}

if (maxHeap.size() > minHeap.size() + 1) {

minHeap.offer(maxHeap.poll());

} else if (maxHeap.size() < minHeap.size()) {

maxHeap.offer(minHeap.poll());

}

rst[i] = maxHeap.peek();

}

return rst;

}

}

```