>  Q&A  >  본문

c++ - n个数,要求插入,查找最大最小值,删除最大最小值的时间复杂度都限制在O(log2n),应该用什么算法?

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

黄舟黄舟2765일 전749

모든 응답(5)나는 대답할 것이다

  • 高洛峰

    高洛峰2017-04-17 14:45:26

    楼上两个答案的出发点不同。

    平衡二叉树可以做到,但是原序列会被排序。
    在C++中,set 和 map 都可以满足要求。

    而线段树可以求出区间最大或者最小值,不需要重新排序。
    没有现成的数据结构可用,你可以自己写个模板。

    회신하다
    0
  • PHP中文网

    PHP中文网2017-04-17 14:45:26

    使用平衡二叉树

    회신하다
    0
  • PHP中文网

    PHP中文网2017-04-17 14:45:26

    你们怎么用平衡二叉树呢,虽然可行;但如果只是最大最小值,那只需要使用一个heap,在C++中有现成数据结构,是STL中的priority_queue

    회신하다
    0
  • 迷茫

    迷茫2017-04-17 14:45:26

    线段树可解 ...

    회신하다
    0
  • 天蓬老师

    天蓬老师2017-04-17 14:45:26

    用C++ STL里的set

    회신하다
    0
  • 취소회신하다