在C++的unordered_map中查找最大密钥

Question

这个问题是类似到this问题，但我需要在unordered_map（hashMap）而不是地图中找到它。由于unordered_map中的元素显然是无序的，因此我不能使用类似问题中提到的逻辑。

那么，有没有一种方法（顺序迭代除外）找出unordered_map中的最大密钥？也就是说，最好在O(1)或O(logN)而不是O(n)？

谢谢！

Answer 1

从其本质来说，无序地图无法轻松提供其最大值，因此，如果无序地图是您拥有的全部地图，则必须按顺序搜索。

但是，没有任何东西阻止您提供自己的自己的类，它从派生自（或包含）无序映射并向其添加功能。在伪代码，含类可以去类似：

class my_int_map: 
    unordered_int_map m_map; # Actual underlying map. 
    int m_maxVal = 0;   # Max value (if m_count > 0). 
    bool m_count = 0;   # Count of items with max value. 

    int getMaxVal(): 
     # No max value if map is empty (throws, but you 
     # could return some sentinel value like MININT). 

     if m_map.size() == 0: 
      throw no_max_value 

     # If max value unknown, work it out. 

     if m_count == 0: 
      m_maxVal = m_map[0] 
      m_count = 0 
      for each item in m_map: 
       if item > m_maxVal: 
        m_maxVal = item 
        m_count = 1 
       else if item == m_maxVal: 
        m_count++ 

     return m_maxVal 

    addVal(int n): 
     # Add it to real map first. 

     m_map.add(n) 

     # If it's only one in map, it's obviously the max. 

     if m_map.size() == 1: 
      m_maxVal = n 
      m_count = 1 
      return 

     # If it's equal to current max, increment count. 

     if m_count > 0 and n == m_maxVal: 
      m_count++ 
      return 

     # If it's greater than current max, fix that. 

     if m_count > 0 and n > m_maxVal: 
      m_maxVal = n 
      m_count = 1 

    delIndex(int index): 
     # If we're deleting a largest value, we just decrement 
     # the count, but only down to zero. 

     if m_count > 0 and m_map[index] == m_maxVal: 
      m_count-- 
     m_map.del(index) 

这是一个标准的优化，它提供了一些财产的惰性评估，同时仍缓存它的速度一定的收藏。

只有当您删除当前值最高的最后一项时，才会发生搜索O(n)。

全部其他操作（获取最大值，添加，删除时不是最后的最大项目）保持最大值更新为O(1)成本。