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

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

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

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

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

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

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

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

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

    Спасибо.

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

    Сразу оговорюсь, я пока плохо разбираюсь в структурах данных. Объясните, пожалуйста, почему O(1), а не logN?

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

    для std::map инкремент или декремент итератора работает в худшем случае за логарифм, из-за это куча людей получает TLE на контестах

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

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

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

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

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

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

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

        Т.е. если в процессе работы с m я везде вместо m[y]=0 буду писать m.erase(y), то можно будет использовать просто m.rbegin()?

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

        Стоит учесть, что при обращении к елементу ему автоматически присваивается значение 0

        → Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

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

    → Ответить