Блог пользователя Obk

максимальный элемент в C++ map
Автор Obk, история, 10 лет назад, По-русски

Нам дан C++ map<int,int> m; Как эффективно вычислить максимальное x, такое что m[x]!=0 и какая асимптотика одного такого вычисления?

Мне в голову приходит запустить цикл for с реверс-итератором и т.к. элементы упорядочены(?), то первое значение как раз и будет x. Даже если это работает, то я совсем не уверен, что это эффективный метод.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
10 лет назад, скрыть # |
 
Проголосовать: нравится +21 Проголосовать: не нравится

*(--m.end()), ну или m.rbegin()

Выполнится за O(1).

→ Ответить
»
10 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +1 Проголосовать: не нравится

Совершенно верно, элементы в map упорядочены. В данном случае они будут упорядочены по возрастанию x. Только for тебе здесь не нужен, можно просто сделать вот так: int ans = (*(m.rbegin())).first (возможно некоторые скобки лишние, не очень хорошо знаю C++, поставил для подстраховки). Единственное, что еще следует учесть — если ты какому-то элементу явно присвоил значение 0, то это может не работать. И насчет асимптотики — обращение к элементу работает за logN, думаю здесь тоже будет логарифм. UPD: Я ошибался. Асимптотика будет O(1).

→ Ответить
  • »
    »
    10 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Спасибо. Единственное, что еще следует учесть — если ты какому-то элементу явно присвоил значение 0, то это может не работать. Знатоки C++, пожалуйста прокомментируйте это утверждение.

    → Ответить
    • »
      »
      »
      10 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +2 Проголосовать: не нравится

      Дело в том, что stl map не хранит никакого значения для тех ключей, которым не присвоено никакого значения. Но если существует такой ключ, для которого значение должно быть равно нулю, то map его не удалит, а удалять его нужно вручную с помощью метода erase. Исправить в вашем случае это можно так:

      while (mp.size() && (*(--mp.end())).second == 0)
       mp.erase(--mp.end());
cout << (--mp.end()) -> first;
      → Ответить
  • »
    »
    10 лет назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится +11 Проголосовать: не нравится

    Можно еще m.rbegin() -> first

    → Ответить