Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Code review Leetcode 295 - median of stream - using SortedSet
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Leetcode295_medianOfStream
{
/// <summary>
/// Leetcode 295:
/// https://leetcode.com/problems/find-median-from-data-stream/#/description
/// Using SortedSet to solve the problem, underneath is binary search tree.
/// A few challenges here:
/// 1. Go over SortedSet in C#, understand API
/// Comparer defintion:
/// Comparer<int[]>.Create((a, b) => a[0] == b[0] ? a[1] - b[1] : a[0] - b[0])
/// Max, Min, Count 3 APIs
///
/// June 6, 2017 Will figure out how to get more familiar with C# SortedSet
///
/// June 29, 2017
/// Read the book Item 31: Implement ordering relations with IComparable<T>
/// and IComparer<T>
/// Book: Effective C# 50 Specific Ways to Improve Your C# Second Edition Scott Meyers
///
/// </summary>
class MedianFinder
{
static void Main(string[] args)
{
//RunTestcase();
RunTestcase2();
}
public static void RunTestcase()
{
var medianFinder = new MedianFinder();
medianFinder.AddNumber(1);
medianFinder.AddNumber(5);
medianFinder.AddNumber(3);
medianFinder.AddNumber(4);
medianFinder.AddNumber(2);
var median = medianFinder.FindMedian();
Debug.Assert(median == 3);
}
public static void RunTestcase2()
{
var medianFinder = new MedianFinder();
medianFinder.AddNumber(1);
medianFinder.AddNumber(5);
medianFinder.AddNumber(3);
medianFinder.AddNumber(4);
medianFinder.AddNumber(2);
medianFinder.AddNumber(6);
var median = medianFinder.FindMedian();
Debug.Assert(Math.Abs(median - 3.5) < 0.001);
}
private int counter = 0;
/// <summary>
/// code review on June 29, 2017 - need to look into SortedSet<IComparer>
///
/// </summary>
private SortedSet<int[]> treeLowerHalf = new SortedSet<int[]>(
Comparer<int[]>.Create((a, b) => a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));
private SortedSet<int[]> treeUpperHalf = new SortedSet<int[]>(
Comparer<int[]>.Create((a, b) => a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));
/// <summary>
/// code review on June 29, 2017
/// Keep two tree same size if there are even numbers. If there are odd numbers,
/// then first tree called treeLowerHalf will have numbers/2 + 1 numbers.
///
/// Need to go over SortedSet API: Add, Remove,
/// Property Max[2] and Min[2]
/// https://msdn.microsoft.com/en-us/library/dd411719(v=vs.110).aspx
/// </summary>
/// <param name="number"></param>
public void AddNumber(int number)
{
var item = new int[] { number, counter++ }; // what is the second number for?
int countLower = treeLowerHalf.Count;
bool isSameSize = countLower == treeUpperHalf.Count;
bool lowerTreeEmpty = countLower == 0;
int maxValueLowerTree = lowerTreeEmpty ? int.MinValue : treeLowerHalf.Max[0];
bool lessThanMaxValueLowerTree = number <= maxValueLowerTree;
if (isSameSize)
{
if (treeLowerHalf.Count == 0 || lessThanMaxValueLowerTree)
{
treeLowerHalf.Add(item);
}
else
{
treeUpperHalf.Add(item);
// move the minimum number from treeUpperHalf to treeLowerHalf.
treeLowerHalf.Add(treeUpperHalf.Min);
treeUpperHalf.Remove(treeUpperHalf.Min);
}
}
else if (lessThanMaxValueLowerTree)
{
treeLowerHalf.Add(item);
// move the maximum number from treeLowerHalf to treeUpperHalf
treeUpperHalf.Add(treeLowerHalf.Max);
treeLowerHalf.Remove(treeLowerHalf.Max);
}
else
{
treeUpperHalf.Add(item);
}
}
/// <summary>
/// Code review on June 29, 2017
/// Return the median of current data stream
/// </summary>
/// <returns></returns>
public double FindMedian()
{
if (treeLowerHalf.Count == 0)
{
return 0;
}
if (treeLowerHalf.Count == treeUpperHalf.Count)
{
return (treeLowerHalf.Max[0] + treeUpperHalf.Min[0]) / 2d;
}
else
{
return treeLowerHalf.Max[0];
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.