[leetCode/JS] 295. Find Median from Data Stream

문제 설명

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

• For example, for arr = [2,3,4], the median is 3.
• For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

• MedianFinder() initializes the MedianFinder object.
• void addNum(int num) adds the integer num from the data stream to the data structure.
• double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

입출력 예

Example 1:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]

Output
[null, null, null, 1.5, null, 2.0]


Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

Explanation
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // return 1
stockSpanner.next(80); // return 1
stockSpanner.next(60); // return 1
stockSpanner.next(70); // return 2
stockSpanner.next(60); // return 1
stockSpanner.next(75); // return 4, because the last 4 prices (including today's price of 75) were less than or equal to today's price.
stockSpanner.next(85); // return 6

Constraints

• -10⁵ <= num <= 10⁵
• There will be at least one element in the data structure before calling findMedian.
• At most 5 * 10⁴ calls will be made to addNum and findMedian.

---

내 솔루션

var MedianFinder = function() {
    this.nums = [];
};

/** 
 * @param {number} num
 * @return {void}
 */
MedianFinder.prototype.addNum = function(num) {
    if (this.nums.length === 0) {
        this.nums.push(num)
        return;
    }
    let low = 0;
    let hight = this.nums.length;
    while (low < hight) {
        const mid = Math.floor((low + hight) / 2);
        if(this.nums[mid] < num) {
            low = mid + 1;
        } else {
            hight = mid;
        }
    }
    this.nums.splice(low, 0, num)
};

/**
 * @return {number}
 */
MedianFinder.prototype.findMedian = function() {
    const mid = Math.floor(this.nums.length / 2);
    if (this.nums.length % 2 === 0) {
        return (this.nums[mid-1] + this.nums[mid]) / 2
    } else {
        return this.nums[mid]
    }
};

감상평

• 왜케 어렵냐..
• array insert 하는건 원래 알던 알고리즘을 기억속에서 힘들게 끄집어 냈다. 이거 몰랐으면 오늘 못 풀었겠다 싶음.
• 다른 미친놈들은 힙 만들어서 최적화했던데 한번 공부해봐야 할 뜻
• 중간 값 찾는건 진짜 오래 고민하다가 이건가 싶어서 하니까 됨.