三刷 06/2022
Version #1 TreeSet
TreeSet里面应该存index而不是数字来防止duplicate
在所有比较的时候注意要比较nums[treeset.last()]/nums[treeset.first()]而不是直接poll出来的value
感觉这一版比之前二刷写的要好
TreeSet remove 是O(logK), add O(logK), first()/last() O(logK)
Time O(NlogK)
Space O(N)
Runtime: 29 ms, faster than 92.07% of Java online submissions for Sliding Window Median.
Memory Usage: 54.8 MB, less than 71.50% of Java online submissions for Sliding Window Median.
class Solution {
public double[] medianSlidingWindow(int[] nums, int k) {
// We use TreeSet to get O(logK) time complexity for removing element
Comparator<Integer> cmp = (a, b) -> nums[a] == nums[b] ? a - b : Integer.compare(nums[a], nums[b]);
TreeSet<Integer> smallerHalf = new TreeSet<>(cmp);
TreeSet<Integer> largerHalf = new TreeSet<>(cmp);
double[] medians = new double[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
add(smallerHalf, largerHalf, nums, i);
// i 0 1 2 -> k = 2
// (1 2) 3
if (i >= k && !smallerHalf.remove(i - k)) {
// remove element i - k
largerHalf.remove(i - k);
}
balance(smallerHalf, largerHalf);
if (i >= k - 1) {
if (k % 2 == 1) {
medians[i - k + 1] = (double)nums[smallerHalf.last()];
} else {
medians[i - k + 1] = nums[smallerHalf.last()] / 2.0 + nums[largerHalf.first()] / 2.0;
}
}
}
return medians;
}
private void add(TreeSet<Integer> smallerHalf, TreeSet<Integer> largerHalf, int[] nums, int index) {
if (smallerHalf.isEmpty() || nums[index] <= nums[smallerHalf.last()]) {
smallerHalf.add(index);
} else {
largerHalf.add(index);
}
}
private void balance(TreeSet<Integer> smallerHalf, TreeSet<Integer> largerHalf) {
if (smallerHalf.size() < largerHalf.size()) {
smallerHalf.add(largerHalf.pollFirst());
}
if (smallerHalf.size() > largerHalf.size() + 1) {
largerHalf.add(smallerHalf.pollLast());
}
}
}
Version #2 TreeSet
36.23 %
还是那个overflow的edge case有问题
这里出现在compareTo(), 若前一个是MIN_VALUE后一个是MAX_VALUE，减完以后直接溢出
所以要cast成double或者long
TreeSet 的remove 是O(logk)
所以Time O(nlogk)
class Tuple implements Comparable<Tuple>{
public int index;
public int val;
public Tuple(int index, int val) {
this.index = index;
this.val = val;
}
@Override
public int compareTo(Tuple other) {
//if indices are equal, then they are equal
if (this.val == other.val) {
return this.index - other.index;
}
return (int)((double)this.val - (double)other.val);
}
}
public class Solution {
public double[] medianSlidingWindow(int[] nums, int k) {
TreeSet<Tuple> maxHeap = new TreeSet<>(Collections.reverseOrder());
TreeSet<Tuple> minHeap = new TreeSet<>();
double[] result = new double[nums.length - k + 1];
/* maxHeap minHeap
(first->largest, last->smallest) (first->smallest, last-> largest)
*/
int start = 0, end = 0;
for (end = 0; end < nums.length; end++) {
Tuple curr = new Tuple(end, nums[end]);
//add end
if (maxHeap.size() == 0 || nums[end] < maxHeap.first().val) {
maxHeap.add(curr);
} else {
minHeap.add(curr);
}
if (end >= k) {
//remove start
start = end - k;
if (nums[start] <= maxHeap.first().val) {
maxHeap.remove(new Tuple(start, nums[start]));
} else {
minHeap.remove(new Tuple(start, nums[start]));
}
}
//System.out.println("size " + maxHeap.size() + " " + minHeap.size());
while (maxHeap.size() < minHeap.size()) {
//System.out.println("temp " + minHeap.last().val);
Tuple temp = minHeap.pollFirst();
maxHeap.add(temp);
}
while (maxHeap.size() > minHeap.size() + 1) {
Tuple temp = maxHeap.pollFirst();
minHeap.add(temp);
}
if (end >= k - 1) {
//System.out.println((double)maxHeap.first().val + " " + (double)minHeap.first().val);
if (maxHeap.size() == minHeap.size()) {
result[end - k + 1] = ((double)maxHeap.first().val + (double)minHeap.first().val) / 2.0;
} else {
result[end - k + 1] = maxHeap.first().val;
}
}
}
return result;
}
}
Version #1 Normal PriorityQueue Version
需要仔细想清楚整个过程
1.加入end，删除start
2.check两个heap的size
3.加入结果
pq实现maxHeap需要写成：
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(1, Collections.reverseOrder());
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
感觉LC的这个题比LintCode稍微复杂一点点
这里给了一个会溢出的testcase
解决办法是在计算过程中就把两个数cast成double
Time
Outer loop O(n)
Inner loop : heap remove O(k)
heap add/peek/poll O(logk)
Over all O(nk)
51.32 %
public class Solution {
public double[] medianSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0) return new double[0];
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(1, Collections.reverseOrder());
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
int start = 0, end = 0;
double[] result = new double[nums.length - k + 1];
for (end = 0; end < nums.length; end++) {
if (maxHeap.size() == 0 || nums[end] < maxHeap.peek()) {
maxHeap.offer(nums[end]);
} else {
minHeap.offer(nums[end]);
}
//[start, end)
if (end >= k) {
start = end - k;
//remove start
if (nums[start] <= maxHeap.peek()) {
maxHeap.remove(nums[start]);
} else {
minHeap.remove(nums[start]);
}
}
//reorganize
int temp;
while (maxHeap.size() < minHeap.size()) {
temp = minHeap.poll();
maxHeap.offer(temp);
}
while (maxHeap.size() > minHeap.size() + 1) {
temp = maxHeap.poll();
minHeap.offer(temp);
}
if (end >= k - 1) {
//System.out.println(maxHeap.size() + " " + minHeap.size());
if (maxHeap.size() == minHeap.size()) {
result[end - k + 1] = ((double)maxHeap.peek() + (double)minHeap.peek()) / 2.0;
} else {
result[end - k + 1] = maxHeap.peek();
}
}
}
return result;
}
}
一刷
下面这个是LintCode版本，跟LC里面对median的定义不太一样
题看错了，调了好久 num num fish
public class Solution {
/**
* @param nums: A list of integers.
* @return: The median of the element inside the window at each moving.
*/
public ArrayList<Integer> medianSlidingWindow(int[] nums, int k) {
// write your code here
ArrayList<Integer> result = new ArrayList<>();
if (nums == null || nums.length == 0 || k <= 0) return result;
//max heap
PriorityQueue<Integer> heap1 = new PriorityQueue<>(1, Collections.reverseOrder());
//min heap
PriorityQueue<Integer> heap2 = new PriorityQueue<>();
int start = 0, end = 0;
int newNum;
int median = nums[0];
for (end = 0; end < nums.length; end++) {
//remove the past element
if (end >= k) {
start = end - k + 1;
if (nums[start - 1] <= heap1.peek()) heap1.remove(nums[start - 1]);
else heap2.remove(nums[start - 1]);
}
//insert the new element
newNum = nums[end];
if (newNum <= median) heap1.offer(newNum);
else heap2.offer(newNum);
if (heap1.size() < heap2.size()) heap1.offer(heap2.poll());
if (heap1.size() > heap2.size() + 1) heap2.offer(heap1.poll());
//System.out.println(heap1.peek() + " " + heap2.peek() + " " + heap1.size() + " " + heap2.size());
median = heap1.peek();
if (end >= k - 1) {
result.add(median);
}
}
return result;
}
}
No comments:
Post a Comment