MedianStream; Part 1

MedianStream_LazyBruteForce.cc

class MedianStream {
 public:
  // Constructor
  MedianStream() {
    numValues = 0;
  }
  
  // Adds integer value to the stream
  void addNumber(int x) {
    numValues++;
    values.push_back(x);
  }
  
  // Returns median of all numbers seen so far
  double getMedian() {
    // Sort values
    sort(values.begin(), values.end());
    
    // Calculate and return the median
    if (numValues % 2 == 0) {
      return (values[(numValues-1)/2] + values[numValues/2])/2.0;
    } else {
      return values[(numValues-1)/2];
    }
  }

 private:
  int numValues;
  vector<int> values;
};