Реализуйте очередь, в которой push_rear (), pop_front () и get_min () - все операции с постоянным временем - PullRequest
Новая
       32

Реализуйте очередь, в которой push_rear (), pop_front () и get_min () - все операции с постоянным временем

73 голосов
/ 26 января 2011

Я сталкивался с таким вопросом: Реализовать очередь, в которой push_rear (), pop_front () и get_min () - все операции с постоянным временем.

Сначала я подумал об использовании min- структура данных кучи, которая имеет сложность O (1) для get_min ().Но push_rear () и pop_front () были бы O (log (n)).

Кто-нибудь знает, что было бы лучшим способом реализовать такую ​​очередь, которая имеет O (1) push (), pop () и min ()?

Я гуглил об этом и хотел указать на этот поток Алгоритм вундеркиндов .Но похоже, что ни одно из решений не следует правилу постоянного времени для всех трех методов: push (), pop () и min ().

Спасибо за все предложения.

Ответы [ 12 ]

0 голосов
/ 30 сентября 2013 
#include <iostream>
#include <queue>
#include <deque>
using namespace std;

queue<int> main_queue;
deque<int> min_queue;

void clearQueue(deque<int> &q)
{
  while(q.empty() == false) q.pop_front();
}

void PushRear(int elem)
{
  main_queue.push(elem);

  if(min_queue.empty() == false && elem < min_queue.front())
  {
      clearQueue(min_queue);
  }

  while(min_queue.empty() == false && elem < min_queue.back())
  {
      min_queue.pop_back();
  }

  min_queue.push_back(elem);
}

void PopFront() 
{
  int elem = main_queue.front();
  main_queue.pop();

  if (elem == min_queue.front())
  {
       min_queue.pop_front();
  }
}

int GetMin() 
{ 
  return min_queue.front(); 
}

int main()
{
  PushRear(1);
  PushRear(-1);
  PushRear(2);

  cout<<GetMin()<<endl;
  PopFront();
  PopFront();
  cout<<GetMin()<<endl;

  return 0;
}
0 голосов
/ 07 августа 2011

Мы знаем, что push и pop являются операциями с постоянным временем [O (1), если быть точным].

Но когда мы думаем о get_min () [то есть, чтобы найти текущее минимальное число в очереди] обычнопервое, что приходит на ум, - это поиск по всей очереди каждый раз, когда делается запрос на минимальный элемент.Но это никогда не даст операции с постоянным временем, которая является главной целью проблемы.

Обычно это задают очень часто в интервью, поэтому вы должны знать хитрость

.нам нужно использовать еще две очереди, которые будут отслеживать минимальный элемент, и мы должны продолжать модифицировать эти 2 очереди, поскольку мы выполняем операции push и pop для очереди, чтобы минимальный элемент был получен за время O (1).

Вот самоописательный код sudo, основанный на упомянутом выше подходе.

    Queue q, minq1, minq2;
    isMinq1Current=true;   
    void push(int a)
    {
      q.push(a);
      if(isMinq1Current)
      {
        if(minq1.empty) minq1.push(a);
        else
        {
          while(!minq1.empty && minq1.top < =a) minq2.push(minq1.pop());
          minq2.push(a);
          while(!minq1.empty) minq1.pop();
          isMinq1Current=false;
        }
      }
      else
      {
        //mirror if(isMinq1Current) branch. 
      }
    }

    int pop()
    { 
      int a = q.pop();
      if(isMinq1Current)
      {
        if(a==minq1.top) minq1.pop();
      }
      else
      {
        //mirror if(isMinq1Current) branch.    
      }
    return a;
    }
Страница:
...