Title:
Find Median from Data Stream - Strategy 1
Link to LeetCode:
https://leetcode.com/problems/find-median-from-data-stream/
Specification:
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.
For example,[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:
Examples:
Example 1:
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
Example 2:
Initial Code and Signature:
public abstract class MedianFinder {
public abstract void addNum(int num);
public abstract double findMedian();
}
Algorithm:
Run-Time Analysis:
GitHub Project:
Code:
import java.util.*;
/**
*
* @author Mahsa Sadi
*
* @since 2020 - 03 - 13
*
* License: Creative Commons
*
* Copyright by Mahsa Sadi
*
*
*/
public class MedianFinderV1 extends MedianFinder {
/**
* Problem:
*
* Find Median from Data Stream
*
*
*
* Description:
*
* 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.
*
*
*
* 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.
*
*
*
*
* Solution:
*
*
* 1- Consider an array list for storing the elements of the data stream.
*
* 2- Keep this array list always sorted upon adding a new element.
*
* 3- Use binary search to find the location where a new element should be inserted.
*
*
*
* Note:
*
* This array list is a high-level data structure in Java,
*
* with a performance between an array of items and a list of items.
*
*
*
* Complexity:
*
* 1- findMedian: O (1);
* 2- addNum: Log (dataStream.size()) + O (dataStream.size ()) = O (N + Log N) = O (N)
*
*
*
*/
List <Integer> dataStream;
public MedianFinderV1 ()
{
dataStream = new ArrayList <Integer> ();
}
@Override
public double findMedian() {
double median;
if (dataStream.size() % 2 == 0)
{
median = (double) ( dataStream.get(dataStream.size() / 2 ) +
dataStream.get( (dataStream.size() / 2) - 1) )
/ 2;
}
else
median = dataStream.get(dataStream.size() / 2);
return median;
}
@Override
public void addNum(int num) {
if (dataStream.isEmpty())
dataStream.add(num);
else
{
int position = findLocationUsingBinarySearch (num, 0 , dataStream.size() - 1 );
dataStream.add(position, num);
}
}
public int findLocationUsingBinarySearch (int num, int start, int end)
{
int middle = (start + end ) / 2;
int middleValue = dataStream.get(middle);
if (num == middleValue)
return middle + 1;
else if (start == end)
{
if (num > dataStream.get(start))
return end + 1;
else
return start;
}
else if (num > middleValue)
{
if (middle != end )
return findLocationUsingBinarySearch (num, middle + 1, end);
else
return findLocationUsingBinarySearch (num, middle, end);
}
else
{
if (start != middle)
return findLocationUsingBinarySearch (num, start, middle - 1);
else
return findLocationUsingBinarySearch (num, start, middle);
}
}
public String toString ()
{
String data ="";
for (Integer element : dataStream)
data += element + " ";
return data;
}
}