首頁猿問面試題，一個(gè)key-value容器...

面試題，一個(gè)key-value容器的實(shí)現(xiàn)問題？

面試數(shù)據(jù)結(jié)構(gòu)

Smart貓小萌 2018-08-01 17:29:18

今天在網(wǎng)上看到了一道別人分享的數(shù)據(jù)結(jié)構(gòu)面試題，要求實(shí)現(xiàn)一個(gè)key-value容器，支持如下操作：1.根據(jù)key獲取元素2.根據(jù)key刪除元素3.插入元素4.根據(jù)value獲取key以上操作時(shí)間復(fù)雜度均要求在O(log N)以內(nèi)。用平衡樹可以實(shí)現(xiàn)前三條，有沒有哪種數(shù)據(jù)結(jié)構(gòu)可以一并實(shí)現(xiàn)第四條的？

查看完整描述

3 回答

qq_花開花謝_0

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

前三個(gè)都很好做，但是第四個(gè)問題描述得不夠清楚，因?yàn)榭赡芏鄠€(gè)key對(duì)應(yīng)的都是相同的value，所以根據(jù)value去獲取key就比較麻煩了，結(jié)果可能是一個(gè)數(shù)組。如果保證一一對(duì)應(yīng)，key和value也都是唯一的，那么像樓上說的簡(jiǎn)單的兩棵平衡樹就可以解決

反對(duì) 回復(fù) 2018-08-05