劍指Offer——資料流中的中位數（JS實作） ｜刷題打卡

前言

掘金團隊号上線，助你 Offer 臨門！ 點選

檢視詳情

題目描述

解題思路

• 這道題屬于考查二分查找
• 本題如果直接采用JS中自帶的排序肯定是要逾時的，要不然LeetCode也不會将這道題歸為困難
• 二分查找的思路定義兩個指針，一個指針指向的是數組元素的第一個下标，另一個指針指向的是數組元素的最後一個元素的下标。
• 中位數下标指的是通過四舍五入的方法，左邊指針的下标 + 右邊指針的下标 / 2然後進行四舍五入，得到的就是中位數下标
• 如果要添加的值大于中位數下标對應的值，左邊的指針移動到中位數指針+1的位置。如果要添加的值小于中位數下标對應的值，右邊的指針移動到中位數指針-1的位置，如果相等則直接添加導緻中位數下标的位置，其餘元素後移。
• 循環的結束條件是左指針＞右指針

解題代碼

var MedianFinder = function() {
    this.stack = [];
};
MedianFinder.prototype.addNum = function(num) {
    if (this.stack.length === 0) {
       this.stack.push(num);
       return; 
    }
    // 定義左指針和右指針 注意：這裡的指針指的都是下标
    let left = 0;
    let right = this.stack.length - 1;
    while (left <= right) {
        // 找到中位數的下标
        let mid = Math.floor((left + right)/2);
        if (num === this.stack[mid]) {
            this.stack.splice(mid,0,num);
            return;
        } else if (num < this.stack[mid]) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    this.stack.splice(right+1,0,num);
};

MedianFinder.prototype.findMedian = function() {
    if (this.stack.length === 0) {
        return [];
    }
    if (this.stack.length % 2 === 0) {
        let len = this.stack.length;
        return (this.stack[len/2] + this.stack[len/2 -1]) / 2
    } else {
        let mid = Math.floor(this.stack.length/2);
        return this.stack[mid];
    }
};
      

總結（本題給我們的啟示思路）

• 啟示一：學會使用二分查找
• 啟示二：學會使用splice插入元素
• 啟示三：通過Math.floor進行四舍五入來求中位數下标