So I came up with the following solution which is(adsbygoogle = window.adsbygoogle || []).push({}); n*log2(n)since the input isnelements and I use a binary insertion and calculating the median is constant time. This is passes all the test cases in the tests that don't time out. I need to figure out how to make it faster so I beat the timeouts. I'm pretty much out of ideas.

Code (Text):

using System;

using System.Collections.Generic;

using System.IO;

using System.Linq;

using System.Diagnostics.Contracts;

namespace Solution

{

static class Extensions

{

public static void BinaryInsertion(this List<int> list, int val)

{

int index = list.BinarySearch(val);

if(index < 0) index = ~index;

list.Insert(index, val);

}

public static double Median(this List<int> list)

{

Contract.Requires(list.Count > 0, "Method only valid for non-empty lists");

int i = list.Count / 2;

double d = list.Count % 2 == 1 ? (double)list[i] : (double)(list[i-1] + list[i]) / 2.0;

return Math.Round(d, 1);

}

}

class Solution

{

static void Main(string[] args)

{

int n = Int32.Parse(Console.ReadLine());

List<int> list = new List<int>();

for(int i = 0; i < n; ++i)

{

int val = Int32.Parse(Console.ReadLine());

list.InsertInOrder(val);

Console.WriteLine(list.Median());

}

}

}

}

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# C/++/# How to do a running median in n*log2(n)?

Tags:

Have something to add?

Draft saved
Draft deleted

Loading...

Similar Threads - running median n*log2 | Date |
---|---|

Python How can I run Python by getting values from Matlab | Mar 7, 2018 |

Running OpenFOAM on a Mac | Dec 13, 2017 |

C/++/# Easy way of counting # processeses running? | Nov 8, 2017 |

FaceBook AI runs away with secret coding of it's own | Aug 1, 2017 |

Find the median of two sorted arrays | Jul 11, 2013 |

**Physics Forums - The Fusion of Science and Community**