首頁(yè) 猿問(wèn) 如何快速找到數(shù)量a的大小處于，數(shù)組...

如何快速找到數(shù)量a的大小處于，數(shù)組b中那個(gè)鍵名與鍵名之間

JavaScript

守候你守候我 2018-08-14 11:10:59

變量a = 8 以及已按大小順序排列好的數(shù)組 b = array(1,3,5,7,8.9,9,11.3);假設(shè)數(shù)組長(zhǎng)度未知,變量值未知，數(shù)組鍵值按從小到大已排列好如何快速找到數(shù)量a的大小處于，數(shù)組b中那個(gè)鍵名與鍵名之間eg: a=8,處于b[4]與b[5]之間

查看完整描述

1 回答

慕容森

TA貢獻(xiàn)1853條經(jīng)驗(yàn) 獲得超18個(gè)贊

長(zhǎng)度未知…………不太可能吧……不就是b.length就完了嗎…………
這種查詢除了二分還有什么更好的方法嗎……

或者自己封裝一個(gè)class，在數(shù)組建立的時(shí)候做一個(gè)映射，把數(shù)據(jù)按照大小分組，怎么分組看你的要求，可以大幅提高速度。
比如簡(jiǎn)單一點(diǎn)，按照整數(shù)分組，像這樣：

class ClassA extends Array {
    constructor(...args) {        super(...args);        this.hash = [];        for(let i = 0; i < this.length; i++) {            if(!this.hash[Math.floor(this[i])]) this.hash[Math.floor(this[i])] = i;
        }
    }
}

數(shù)組還是那個(gè)數(shù)組不變，只是添加一個(gè)hash，里面代表的是整數(shù)段的起始下標(biāo)，比如你要查詢8.5這個(gè)數(shù)，那么只需要查詢this.hash[Math.floor(8.5)]和this.hash[Math.floor(8.5) + 1]，兩個(gè)下標(biāo)之間的數(shù)據(jù)就行了，假如這倆hash里面是空的，那么分別往前、往后找就行，直到找到值為止。要是數(shù)據(jù)過(guò)于稀疏，那么可以給這個(gè)hash再做一個(gè)hash，記錄有效整數(shù)段，反正就是空間換時(shí)間啦。

反對(duì) 回復(fù) 2018-09-19