Блог

Я столкнулся с этим вопросом, где цель состоит в том, чтобы создать класс с двумя методами — get() и set_range(x, y) .

Поведение обоих методов объясняется в комментариях ниже, и также есть примеры.

 class UniqueRandomGenerator {  int start, end;   public:  int get() {  // Returns a unique random number in the range [start, end].   // Every call should return a different random number unless there   // is no number left to be returned within the range [start, end].   // When all numbers within [start, end] are already returned at least once,  // the range is reset and then it is ok to return the previously returned   // number.  }   void set_range(int s, int e) {  // Update the range [start, end] to be [s, e].   // However, the random numbers returned by get() should still be unique.   // Only when there is no number left in [s, e], we can repeat the numbers.  }  };   

Например:

 set_range(5, 8); get(); // returns one of {5, 6, 7, 8}. Say it returns 6 set_range(3, 6); get(); // must return one of {3, 4, 5}. Note that 6 is not there because it   // returned previously. Say it returns 3. get(); // One of {4, 5}. Say 4. get(); // One of {5}. Must be 5. get(); // Because there is no number left, range gets reset. Now one of {3, 4, 5, 6}  // should be returned.  

• Если есть только get() операция для поддержки и диапазон постоянен

Подход 1 — Я могу перетасовать массив один раз и продолжать возвращать следующее число из массива. Когда я дойду до конца, я снова перетасую массив и начну возвращать число с самого начала.

Подход 2 — Я могу добавлять числа из [начало, конец] в массив и случайным образом генерировать индекс между 0 до array.size()-1 . Верните номер по этому индексу. Замените этот индекс последним индексом, а затем уменьшите размер массива.

В обоих вышеперечисленных подходах существует предварительная O(n) стоимость, даже если амортизированная временная сложность O(1) для каждого get() из них . Если звонков очень мало get() , то заранее O(n) звонить не желательно.

Есть ли способ разделить эту первоначальную стоимость на несколько get() звонков?

Подход 3 — У меня может быть набор, в котором я могу отслеживать все возвращенные номера. Изначально он будет пустым. Я могу сгенерировать случайное число и посмотреть, присутствует ли оно в наборе. Если его нет, я добавлю его в набор и верну. В противном случае я сгенерирую другое число.

Проблема с этим подходом заключается в том, что нет верхней границы того, сколько раз мне придется генерировать случайные числа, пока я не найду уникальное.

Все вышеперечисленные подходы работают, если вообще работают, только когда диапазон постоянен. Добавление set_range() , по моему мнению, делает это намного сложнее.

Каковы эффективные способы обработки обоих get() вызовов и set_range() вызовов?