8000 refactor 480 · sreekanthrcs62/Leetcode@16f3398 · GitHub
[go: up one dir, main page]
Skip to content

Commit 16f3398

Browse files
fishercoder1534fishercoder1534
committed
refactor 480
1 parent 72ae5fd commit 16f3398

File tree

2 files changed

+61
-57
lines changed

2 files changed

+61
-57
lines changed

‎src/main/java/com/fishercoder/solutions/_480.java

Lines changed: 58 additions & 54 deletions
Original file line numberDiff line numberDiff line change
@@ -35,69 +35,73 @@
3535
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.
3636
*/
3737
public class _480 {
38-
39-
/**You cannot simply use minus sign '-' to denote the descending order, because e.g. 3 and -3 might both exist in this array,
40-
* so we'll have to use the original numbers themselves to store in the heaps.*/
41-
private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
42-
private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
43-
44-
public double[] medianSlidingWindow(int[] nums, int k) {
45-
int n = nums.length - k + 1;
46-
if (n <= 0) {
47-
return new double[0];
48-
}
49-
double[] result = new double[n];
50-
51-
for (int i = 0; i <= nums.length; i++) {
52-
if (i >= k) {
53-
result[i - k] = getMedian();
54-
remove(nums[i - k]);
38+
public static class Solution1 {
39+
40+
/**
41+
* You cannot simply use minus sign '-' to denote the descending order, because e.g. 3 and -3 might both exist in this array,
42+
* so we'll have to use the original numbers themselves to store in the heaps.
43+
*/
44+
private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
45+
private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
46+
47+
public double[] medianSlidingWindow(int[] nums, int k) {
48+
int n = nums.length - k + 1;
49+
if (n <= 0) {
50+
return new double[0];
5551
}
56-
if (i < nums.length) {
57-
add(nums[i]);
52+
double[] result = new double[n];
53+
54+
for (int i = 0; i <= nums.length; i++) {
55+
if (i >= k) {
56+
result[i - k] = getMedian();
57+
remove(nums[i - k]);
58+
}
59+
if (i < nums.length) {
60+
add(nums[i]);
61+
}
5862
}
59-
}
6063

61-
return result;
62-
}
63-
64-
private double getMedian() {
65-
if (maxHeap.isEmpty() && minHeap.isEmpty()) {
66-
return 0;
64+
return result;
6765
}
6866

69-
if (maxHeap.size() == minHeap.size()) {
70-
return ((double)maxHeap.peek() + (double)minHeap.peek()) / 2.0;
71-
} else {
72-
return (double)minHeap.peek();
73-
}
74-
}
67+
private double getMedian() {
68+
if (maxHeap.isEmpty() && minHeap.isEmpty()) {
69+
return 0;
70+
}
7571

76-
private void remove(int num) {
77-
if (num < getMedian()) {
78-
maxHeap.remove(num);
79-
} else {
80-
minHeap.remove(num);
81-
}
82-
if (maxHeap.size() > minHeap.size()) {
83-
minHeap.add(maxHeap.poll());
84-
}
85-
if (minHeap.size() - maxHeap.size() > 1) {
86-
maxHeap.add(minHeap.poll());
72+
if (maxHeap.size() == minHeap.size()) {
73+
return ((double) maxHeap.peek() + (double) minHeap.peek()) / 2.0;
74+
} else {
75+
return (double) minHeap.peek();
76+
}
8777
}
88-
}
8978

90-
private void add(int num) {
91-
if (num < getMedian()) {
92-
maxHeap.add(num);
93-
} else {
94-
minHeap.add(num);
95-
}
96-
if (maxHeap.size() > minHeap.size()) {
97-
minHeap.add(maxHeap.poll());
79+
private void remove(int num) {
80+
if (num < getMedian()) {
81+
maxHeap.remove(num);
82+
} else {
83+
minHeap.remove(num);
84+
}
85+
if (maxHeap.size() > minHeap.size()) {
86+
minHeap.add(maxHeap.poll());
87+
}
88+
if (minHeap.size() - maxHeap.size() > 1) {
89+
maxHeap.add(minHeap.poll());
90+
}
9891
}
99-
if (minHeap.size() - maxHeap.size() > 1) {
100-
maxHeap.add(minHeap.poll());
92+
93+
private void add(int num) {
94+
if (num < getMedian()) {
95+
maxHeap.add(num);
96+
} else {
97+
minHeap.add(num);
98+
}
99+
if (maxHeap.size() > minHeap.size()) {
100+
minHeap.add(maxHeap.poll());
101+
}
102+
if (minHeap.size() - maxHeap.size() > 1) {
103+
maxHeap.add(minHeap.poll());
104+
}
101105
}
102106
}
103107

‎src/test/java/com/fishercoder/_480Test.java

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -10,21 +10,21 @@
1010
* Created by fishercoder on 5/27/17.
1111
*/
1212
public class _480Test {
13-
private static _480 test;
13+
private static _480.Solution1 solution1;
1414
private static int[] nums;
1515
private static double[] expected;
1616
private static int k;
1717

1818
@BeforeClass
1919
public static void setup() {
20-
test = new _480();
20+
solution1 = new _480.Solution1();
2121
}
2222

2323
@Test
2424
public void test1() {
2525
nums = new int[]{1, 3, -1, -3, 5, 3, 6, 7};
2626
expected = new double[]{1, -1, -1, 3, 5, 6};
2727
k = 3;
28-
assertArrayEquals(expected, test.medianSlidingWindow(nums, k), 0);
28+
assertArrayEquals(expected, solution1.medianSlidingWindow(nums, k), 0);
2929
}
3030
}

0 commit comments

Comments
 (0)
0