简体中文(ZH-CN) English(EN) 繁体中文(ZH-TW) 日本語(JA) 한국어(KO) Melayu(MS) Français(FR) Deutsch(DE)
c++ - n个数，要求插入，查找最大最小值，删除最大最小值的时间复杂度都限制在O(log2n)，应该用什么算法？
黄舟
黄舟 2017-04-17 14:43:26
0
5
696

n个数，要求插入，查找最大最小值，删除最大最小值的时间复杂度都限制在O(log2n)，应该用什么算法和数据结构？

黄舟
黄舟

人生最曼妙的风景，竟是内心的淡定与从容！

全部回覆(5)
小葫芦
小葫芦2017-04-17 14:45:26 5樓

樓上兩個答案的出發點不同。

平衡二元樹可以做到，但是原始序列會被排序。
在C++中，set 和 map 都可以滿足要求。

而線段樹可以求區間最大值或最小值，不需要重新排序。
沒有現成的資料結構可用，你可以自己寫個範本。

點贊 +0
新增回覆
洪涛
洪涛2017-04-17 14:45:26 4樓

使用平衡二元樹

點贊 +0
新增回覆
洪涛
洪涛2017-04-17 14:45:26 3樓

你們怎麼用平衡二元樹呢，雖然可行；但如果只是最大最小值，那隻需要使用一個heap，在C++中有現成資料結構，是STL中的priority_queue。

點贊 +0
新增回覆
迷茫
迷茫2017-04-17 14:45:26 2樓

線段樹可解 ...

點贊 +0
新增回覆
Peter_Zhu
Peter_Zhu2017-04-17 14:45:26 1樓

用C++ STL裡的set

點贊 +0
新增回覆
熱門專題
更多>
熱門文章
熱門教學
更多>
相關教學
熱門推薦
最新課程
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板
關於我們 免責聲明 Sitemap
PHP中文網：公益線上PHP培訓，幫助PHP學習者快速成長！