Действительно ли возможно найти два числа, различие которых минимально в O (n) время

Question

Действительно ли возможно найти два числа, различие которых минимально в O (n) время

Довольно скрытая функция - то, что можно определить переменные в, если условие и его объем еще охватят только по если, и блоки:

if(int * p = getPointer()) {
    // do something
}

Некоторое использование макросов, что, например, для обеспечения некоторого "заблокированного" объема как это:

struct MutexLocker { 
    MutexLocker(Mutex&);
    ~MutexLocker(); 
    operator bool() const { return false; } 
private:
    Mutex &m;
};

#define locked(mutex) if(MutexLocker const& lock = MutexLocker(mutex)) {} else 

void someCriticalPath() {
    locked(myLocker) { /* ... */ }
}

Также BOOST_FOREACH использует его под капотом. Для завершения этого это не только возможно в если, но также и в переключателе:

switch(int value = getIt()) {
    // ...
}

и в некоторое время цикле:

while(SomeThing t = getSomeThing()) {
    // ...
}

(и также в для условия). Но я не слишком уверен, являются ли они всем этим полезным:)

23

algorithm optimization

задан Johan - reinstate Monica 24 September 2011 в 22:31

8 ответов

Я думаю, что это возможно. Секрет в том, что на самом деле вам не нужно сортировать список, вам просто нужно создать список существующих чисел. Это может считаться "предположением" с алгоритмической точки зрения, но не с практической точки зрения. Мы знаем, что целые числа ограничены минимальным и максимальным значением.

Итак, создайте массив из 2-битных элементов, по 1 паре для каждого целого числа от INT_MIN до INT_MAX включительно, установите для всех их значение 00.

Итерируйте через весь список номеров. Для каждого числа в списке, если соответствующие 2 бита равны 00, установите их на 01. Если они 01, установите их на 10. В противном случае игнорируйте. Очевидно, это O (n).

Затем, если какой-либо из двух битов установлен в 10, это ваш ответ. Минимальное расстояние равно 0, потому что список содержит повторяющееся число. Если не, Просмотрите список и найдите минимальное расстояние. Многие люди уже указали, что для этого существуют простые алгоритмы O (n).

Итак, O (n) + O (n) = O (n).

Изменить: отвечать на комментарии.

Интересные моменты . Я думаю, что вы могли бы достичь тех же результатов, не делая никаких предположений, сначала найдя min / max списка и используя разреженный массив от min до max для хранения данных. Учитывает предположение INT_MIN / MAX, пространственную сложность и временную сложность O (m) сканирования массива.

Я думаю, что вы могли бы достичь тех же результатов, не делая никаких предположений, сначала найдя минимальное / максимальное значение списка и используя разреженный массив в диапазоне от min до max для хранения данных. Учитывает предположение INT_MIN / MAX, пространственную сложность и временную сложность O (m) сканирования массива.

Я думаю, что вы могли бы достичь тех же результатов, не делая никаких предположений, сначала найдя min / max списка и используя разреженный массив от min до max для хранения данных. Учитывает предположение INT_MIN / MAX, пространственную сложность и временную сложность O (m) сканирования массива.

2