Алгоритм для нахождения 2 объектов с данным различием в массиве
opendir(D, "/path/to/directory") || die "Can't open directory: $!\n"; while (my $f = readdir(D)) { print "\$f = $f\n"; } closedir(D);Править: О, извините, пропущенный "в массив" часть:
my $d = shift; opendir(D, "$d") || die "Can't open directory $d: $!\n"; my @list = readdir(D); closedir(D); foreach my $f (@list) { print "\$f = $f\n"; }EDIT2: большинство других ответов действительно, но я хотел прокомментировать этот ответ а именно, в котором предлагается это решение:
opendir(DIR, $somedir) || die "Can't open directory $somedir: $!"; @dots = grep { (!/^\./) && -f "$somedir/$_" } readdir(DIR); closedir DIR;Во-первых, к документу, что это делает, так как плакат не сделал: это передает возвращенный список от readdir () через grep (), который только возвращает те значения, которые являются файлами (в противоположность каталогам, устройствам, именованным каналам, и т.д.) и которые не начинаются с точки (который делает имя списка
@dotsпри введении в заблуждение, но это происходит из-за изменения, которое он внес при копировании его с readdir () документация). Так как это ограничивает содержание каталога, который это возвращает, я не думаю, что это - технически корректный ответ на этот вопрос, но это иллюстрирует, что общая идиома раньше фильтровала имена файлов в Perl, и я думал, что это будет ценно к документу. Другой пример, замеченный, много:@list = grep !/^\.\.?$/, readdir(D);Этот отрывок читает все содержание из дескриптора каталога D кроме'.' и '..', так как это очень редко желаемо, чтобы использоваться в списке.
2 ответа
woo Я понял! Уловка заключается в Принципе голубятни.
Хорошо ... думайте о числах как о точках на линии. Затем min (A) и max (A) определяют соответственно начальную и конечную точки линии. Теперь разделите эту строку на n равных интервалов длины (max (A) -min (A)) / n . Так как имеется n + 1 точек, две из них должны попасть в один из интервалов.
Обратите внимание, что нам не нужно полагаться на вопрос, говорящий нам, что есть две точки, которые удовлетворяют критерию критерий. Есть всегда две точки, которые ему удовлетворяют.
Сам алгоритм: здесь вы можете использовать упрощенную форму сортировки корзин, поскольку вам нужен только один элемент на корзину (нажмите два, и все готово) . Сначала выполните один цикл по массиву, чтобы получить min (A) и max (A) , и создать целочисленный массив buckets [n] , инициализированный некоторым значением по умолчанию, скажем -1 . Затем выполните второй проход:
for (int i=0; i<len; i++) {
int bucket_num = find_bucket(array[i]);
if (bucket[bucket_num] == -1)
bucket[bucket_num] = i;
else
// found pair at (i, bucket[bucket_num])
}
Где find_bucket (x) возвращает округленный целочисленный результат x / ((max (A) -min (A)) / n) .
min (A) и max (A) , и создать целочисленный массив buckets [n] , инициализированный некоторым значением по умолчанию, скажем -1 . Затем выполните второй проход:
for (int i=0; i<len; i++) {
int bucket_num = find_bucket(array[i]);
if (bucket[bucket_num] == -1)
bucket[bucket_num] = i;
else
// found pair at (i, bucket[bucket_num])
}
Где find_bucket (x) возвращает округленный целочисленный результат x / ((max (A) -min (A)) / n) .
min (A) и max (A) , и создать целочисленный массив buckets [n] , инициализированный некоторым значением по умолчанию, скажем -1 . Затем выполните второй проход:
for (int i=0; i<len; i++) {
int bucket_num = find_bucket(array[i]);
if (bucket[bucket_num] == -1)
bucket[bucket_num] = i;
else
// found pair at (i, bucket[bucket_num])
}
Где find_bucket (x) возвращает округленный целочисленный результат x / ((max (A) -min (A)) / n) .
Давайте переформулируем проблему: мы должны найти два элемента, такие что abs (xy) < = c , где c - константа, которую мы можем найти за O (n) время. (Действительно, мы можем вычислить как max (A) , так и min (A) за линейное время и просто присвоить c = (max-min) / n ) .
Представим, что у нас есть набор сегментов, так что в первом сегменте размещаются элементы 0 <= x c <= x <= 2c и т. Д. Для каждого элемента мы можем определить его ведро за O (1) времени. Обратите внимание, что количество занятых сегментов будет не больше, чем количество элементов в массиве.
Давайте переберем массив и поместим каждый элемент в его корзину. Если в ведро мы собираемся поместить его, там уже есть другой элемент, тогда мы ' мы только что нашли правильную пару x и y !
Если мы повторили весь массив и каждый элемент попал в свою корзину, не беспокойтесь! Выполните итерацию сегментов сейчас (их не более n сегментов, как мы сказали выше) и для каждого элемента сегмента x , если в следующем сегменте y такой элемент, что abs (xy) <= c , то мы нашли решение.
Если мы повторили все сегменты и не нашли подходящих элементов, то решения нет. ] Боже мой, я действительно пропустил этот ящик (см. другой ответ ).
Бакеты могут быть реализованы как хэш-карта, где каждая корзина содержит один индекс массива (размещение элемента в корзине будет выглядеть так: сегментов [a [i] / c] = i ). Мы вычисляем c за O (n) времени, назначаем элементы сегментам за O (n) * O (1) время ( O (1 ) - это доступ к хэш-карте), обход сегментов за O (n) раз. Следовательно, весь алгоритм является линейным.