Алгоритм, чтобы определить, содержит ли массив n … n+m?

Я видел этот вопрос в Reddit, и не было никаких положительных решений, представленных, и я думал, что это будет идеальный вопрос спросить здесь. Это было в потоке о вопросах об интервью:

Запишите метод, который берет международный массив размера m и возвраты (Истинные/Ложные), если массив состоит из чисел n... n+m-1, всех чисел в том диапазоне и только чисел в том диапазоне. Массив, как гарантируют, не будет отсортирован. (Например, {2,3,4} возвратил бы true. {1,3,1} возвратил бы false, {1,2,4} возвратит false.

Проблема, которую я имел с этим, состоит в том, что мой интервьюер продолжал просить, чтобы я оптимизировал (быстрее O (n), меньше памяти, и т.д.), до такой степени, когда он утверждал, что Вы могли сделать это в одной передаче массива с помощью постоянного объема памяти. Никогда не понимал это один.

Наряду с Вашими решениями укажите, предполагают ли они, что массив содержит уникальные объекты. Также укажите, предполагает ли Ваше решение, что последовательность запускается в 1. (Я изменил вопрос немного для разрешения случаев, куда он идет 2, 3, 4...),

править: Я теперь имею мнение, что там не существует линейное вовремя и постоянный в алгоритме пространства, который обрабатывает дубликаты. Кто-либо может проверить это?

Дублирующаяся проблема сводится к тестированию, чтобы видеть, содержит ли массив дубликаты в O (n) время, O (1) пространство. Если это может быть сделано, можно просто протестировать сначала и при отсутствии дубликатов, выполняет отправленные алгоритмы. Таким образом, можно ли протестировать на простофиль в O (n) время O (1) пространство?

45
задан 10 revs, 6 users 94% 18 October 2011 в 09:22
поделиться

32 ответа

Под числами предположения меньше чем один не позволяется и нет никаких дубликатов, существуют простые идентификационные данные суммирования для этого - сумма чисел от 1 до m в инкрементах 1 (m * (m + 1)) / 2. Можно тогда суммировать массив и использовать эти идентификационные данные.

можно узнать, существует ли простофиля под вышеупомянутыми гарантиями плюс гарантия, никакое число не выше m или меньше, чем n (который может быть проверен в O(N))

идея в псевдокоде:
0) Запускаются в N = 0
, 1) Берут Энный элемент в списке.
2), Если это не находится в правильном месте, если список был отсортирован, проверьте, где это должно быть.
3), Если место, где это должно быть уже, имеет то же число, у Вас есть простофиля - TRUE
4 ВОЗВРАТА), Иначе, подкачайте числа (для помещения первого числа на правильное место).
5) С числом Вы просто подкачали с, он в правильном месте?
6), Если не, вернитесь к шагу два.
7) Иначе, запустите на шаге один с N = N + 1. Если это прошло бы конец списка, у Вас нет простофиль.

И, да, который работает в O(N), хотя это может быть похожим O(N ^ 2)

Примечание всем (материал, собранный из комментариев)

Это решение работы под предположением, Вы можете изменить массив, затем используете оперативный вид Основания (который достигает O(N) скорость).

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

Новое понимание (хорошо, больше размышлений, которые не помогают решить ее, но интересны и я ложусь спать):

Так, это было упомянуто, чтобы, возможно, использовать сумму + сумма квадратов. Никто не знал, работало ли это или нет, и я понял, что это только становится проблемой когда (x + y) = (n + m), такие как факт 2 + 2 = 1 + 3. Квадраты также имеют эту проблему благодаря [1 111], Пифагореец утраивается (так 3^2 + 4^2 + 25^2 == 5^2 + 7^2 + 24^2, и сумма квадратов не работает). Если мы используем Великая теорема Ферма , мы знаем, что этого не может произойти для n^3. Но мы также не знаем, нет ли никакого x + y + z = n для этого (если мы не делаем и я не знаю это). Так никакая гарантия это также не повреждается - и если мы продолжаем вниз этот путь, у нас быстро заканчиваются биты.

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

<час>

я должен сказать, нахождение, что контрпримеры иногда намного легче, чем доказательство вещей! Рассмотрите следующие последовательности, все из которых имеют сумму 28 и сумму квадратов 140:

[1, 2, 3, 4, 5, 6, 7]
[1, 1, 4, 5, 5, 6, 6] 
[2, 2, 3, 3, 4, 7, 7]

я не мог найти никакие подобные примеры длины 6 или меньше. Если Вы хотите пример, который имеет надлежащую минуту и макс. значения также, попробуйте эту из длины 8:

[1, 3, 3, 4, 4, 5, 8, 8]
<час>

Более простой подход (изменяющий идею hazzen):

целочисленный массив длины m содержит все числа от n до n+m-1 точно однажды эквивалентности

  • , каждый элемент массива между n и n+m-1
  • , там не дубликаты

(Причина: существуют только m значения в данном целочисленном диапазоне, поэтому если массив содержит m уникальные значения в этом диапазоне, это должно содержать каждые из них однажды)

, Если Вам разрешают изменить массив, можно проверить обоих в одну передачу через список с измененной версией идеи алгоритма hazzen (нет никакой потребности сделать любое суммирование):

  • Для всех индексов массива i от 0 до m-1 делают
    1. Если массив [я] < n или массив [я]> = n+m => ВОЗВРАЩАЮ FALSE ("значение из диапазона, найденного")
    2. , Вычисляют j = массив [я] - n (это - положение на основе 0 массива, до которого [я] в отсортировал массив со значениями от n n+m-1)
    3. , В то время как j не равен мне
        <литий>, Если список [я] равен для списка [j] =>, ВОЗВРАЩАЮТ FALSE ("дубликат, найденный") <литий> список Подкачки [я] со списком [j] <литий> Повторно вычисляю j = массив [я] - n
  • TRUE

ВОЗВРАТА, я не уверен, говорит ли модификация исходного массива против максимального предоставленного дополнительного пространства O (1), но если это не делает это должно быть решением исходный требуемый плакат.

18
ответ дан 9 revs, 3 users 58% 26 November 2019 в 21:31
поделиться

ciphwn имеет его правильный. Это - все, чтобы сделать со статистикой. То, что спрашивает вопрос, в статистических терминах, то, действительно ли форма последовательности чисел дискретное равномерное распределение. Дискретное равномерное распределение состоит в том, где все значения конечного множества возможных значений одинаково вероятны. К счастью, существуют некоторые полезные формулы, чтобы определить, универсален ли дискретный набор. Во-первых, для определения среднего из набора (a.. b) (a+b)/2, и различие (n.n-1)/12. Затем, определите различие данного набора:

variance = sum [i=1..n] (f(i)-mean).(f(i)-mean)/n

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

Ссылки:

0
ответ дан 2 revs, 2 users 81% 26 November 2019 в 21:31
поделиться

Массив содержит числа N, и Вы хотите определить, суммируют ли два из чисел к данному номеру K. Например, если вход 8,4, 1,6, и K равняется 10, ответ - да (4 и 6). Число может использоваться дважды. Сделайте следующее. a. Даете O (N2) алгоритм для решения этой проблемы. b. Даете O (N, регистрируют N), алгоритм для решения этой проблемы. (Подсказка: Отсортируйте объекты сначала. После выполнения так, можно решить проблему в линейное время.) c. Кодируйте оба решения и сравните время выполнения Ваших алгоритмов. 4.

0
ответ дан khaled 26 November 2019 в 21:31
поделиться

Версия C [1 113] решение

Ruby Kent Fredric (для упрощения тестирования)

Контрпример (для версии C): {8, 33, 27, 30, 9, 2, 35, 7, 26, 32, 2, 23, 0, 13, 1, 6, 31, 3, 28, 4, 5, 18, 12, 2, 9, 14, 17, 21, 19, 22, 15, 20, 24, 11, 10, 16, 25}. Здесь n=0, m=35. Эта последовательность промахи 34 и имеет два 2.

Это - O (m) вовремя и O (1) в решении для пространства.

значения Из диапазона легко обнаруживаются в O (n) вовремя и O (1) в пространстве, поэтому тесты сконцентрированы на в диапазоне (означает, что все значения находятся в допустимом диапазоне [n, n+m)), последовательности. Иначе {1, 34} встречный пример (для версии C, sizeof (интервал) == 4, стандартное двоичное представление чисел).

основное различие между C и версией Ruby: << оператор повернет значения в C из-за конечного sizeof (интервал), но в Ruby числа вырастут для размещения результата, например,

Ruby: 1 << 100 # -> 1267650600228229401496703205376

C: int n = 100; 1 << n // -> 16

В Ruby: check_index ^= 1 << i; эквивалентно [1 111]. Тот же эффект мог быть реализован в C++: vector<bool> v(m); v[i] = true;

bool isperm_fredric(int m; int a[m], int m, int n)
{
  /**
     O(m) in time (single pass), O(1) in space,
     no restriction on n,
     ?overflow?
     a[] may be readonly
   */
  int check_index = 0;
  int check_value = 0;

  int min = a[0];
  for (int i = 0; i < m; ++i) {

    check_index ^= 1 << i;
    check_value ^= 1 << (a[i] - n); //

    if (a[i] < min)
      min = a[i];
  }
  check_index <<= min - n; // min and n may differ e.g., 
                           //  {1, 1}: min=1, but n may be 0.
  return check_index == check_value;
}

Значения вышеупомянутой функции были протестированы против следующего кода:

bool *seen_isperm_trusted  = NULL;
bool isperm_trusted(int m; int a[m], int m, int n)
{
  /** O(m) in time, O(m) in space */

  for (int i = 0; i < m; ++i) // could be memset(s_i_t, 0, m*sizeof(*s_i_t));
    seen_isperm_trusted[i] = false;

  for (int i = 0; i < m; ++i) {

    if (a[i] < n or a[i] >= n + m)
      return false; // out of range

    if (seen_isperm_trusted[a[i]-n])
      return false; // duplicates
    else
      seen_isperm_trusted[a[i]-n] = true;
  }

  return true; // a[] is a permutation of the range: [n, n+m)
}

Входные массивы сгенерированы с:

void backtrack(int m; int a[m], int m, int nitems)
{
  /** generate all permutations with repetition for the range [0, m) */
  if (nitems == m) {
    (void)test_array(a, nitems, 0); // {0, 0}, {0, 1}, {1, 0}, {1, 1}
  }
  else for (int i = 0; i < m; ++i) {
      a[nitems] = i;
      backtrack(a, m, nitems + 1);
    }
}
0
ответ дан 12 revs, 2 users 98% 26 November 2019 в 21:31
поделиться

Ответ от "nickf" dows не работает, если массив не отсортирован var_dump (testArray (массив (5, 3, 1, 2, 4), 1, 5));//дает "дубликаты"!!!!

Также Ваша формула для вычисления суммы ([n... n+m-1]) выглядит неправильной...., корректная формула (m (m+1)/2 - n (n-1)/2)

0
ответ дан lalitm 26 November 2019 в 21:31
поделиться

Почему другие решения используют суммирование каждого значения? Я думаю, что это опасно, потому что, когда Вы добавляете вместе O (n) объекты в одно число, Вы технически используете больше, чем O (1) пространство.

Более простой метод:

Шаг 1, выясните, существуют ли какие-либо дубликаты. Я не уверен, возможно ли это в O (1) пространство. Так или иначе возвратите false, если существуют дубликаты.

Шаг 2, выполните итерации через список, отслеживайте самый низкий и самый высокий объекты.

Шаг 3, Делает (самый высокий - самый низкий), равняются m? Если так, возвратите true.

2
ответ дан 2 revs 26 November 2019 в 21:31
поделиться

Алгоритм любой-передачи требует Омеги (n) биты устройства хранения данных.

предположим об обратном, что там существует алгоритм с одной передачей, который использует o (n) биты. Поскольку это делает только одну передачу, это должно суммировать первые значения n/2 в o (n) пространство. С тех пор существуют C (n, n/2) = 2^Theta (n) возможные наборы значений n/2, оттянутых из S = {1..., n}, там существуйте, два отличных набора A и B n/2 оценивают таким образом, что состояние памяти является тем же после обоих. Если' = S \A является "корректным" набором значений к дополнению A, то алгоритм не может возможно ответить правильно за исходные данные

А' - да

B' - никакой

, так как это не может отличить первый случай от второго.

Q.E.D.

2
ответ дан Dave 26 November 2019 в 21:31
поделиться

Провалите меня, если я неправ, но я думаю, что мы можем определить, существуют ли дубликаты или не использование различия. Поскольку мы знаем среднее заранее (n + (m-1)/2, или что-то как этот) мы можем просто подвести итог чисел и квадрата различия, чтобы означать видеть, соответствует ли сумма уравнению (млн + m (m-1)/2), и различие (0 + 1 + 4 +... + (m-1) ^2)/m. Если различие не соответствует, вероятно, что у нас есть дубликат.

РЕДАКТИРОВАНИЕ: различие, как предполагается, (0 + 1 + 4 +... + [(m-1)/2] ^2) *2/m, потому что половина элементов является меньше, чем среднее и другая половина больше, чем среднее.

, Если существует дубликат, термин на вышеупомянутом уравнении будет отличаться от корректной последовательности, даже если другой дубликат полностью уравновесит изменение в среднем. Таким образом, функция возвращает true, только если и сумма и различие соответствуют значениям desrired, которые мы можем вычислить заранее.

1
ответ дан 2 revs 26 November 2019 в 21:31
поделиться

Вот рабочее решение в O (n)

, Это использует псевдокод, предложенный Hazzen плюс некоторые мои собственные идеи. Это работает на отрицательные числа также и не требует никакого материала sum-of-the-squares.

function testArray($nums, $n, $m) {
    // check the sum. PHP offers this array_sum() method, but it's
    // trivial to write your own. O(n) here.
    if (array_sum($nums) != ($m * ($m + 2 * $n - 1) / 2)) {
        return false;    // checksum failed.
    }
    for ($i = 0; $i < $m; ++$i) {
        // check if the number is in the proper range
        if ($nums[$i] < $n || $nums[$i] >= $n + $m) {
            return false;  // value out of range.
        }

        while (($shouldBe = $nums[$i] - $n) != $i) {
            if ($nums[$shouldBe] == $nums[$i]) {
                return false;    // duplicate
            }
            $temp = $nums[$i];
            $nums[$i] = $nums[$shouldBe];
            $nums[$shouldBe] = $temp;
        }
    }
    return true;    // huzzah!
}

var_dump(testArray(array(1, 2, 3, 4, 5), 1, 5));  // true
var_dump(testArray(array(5, 4, 3, 2, 1), 1, 5));  // true
var_dump(testArray(array(6, 4, 3, 2, 0), 1, 5));  // false - out of range
var_dump(testArray(array(5, 5, 3, 2, 1), 1, 5));  // false - checksum fail
var_dump(testArray(array(5, 4, 3, 2, 5), 1, 5));  // false - dupe
var_dump(testArray(array(-2, -1, 0, 1, 2), -2, 5)); // true
1
ответ дан nickf 26 November 2019 в 21:31
поделиться

Некоторое время назад я слышал об очень умном алгоритме сортировки от кого-то, кто работал на телефонную компанию. Они должны были отсортировать крупное количество номеров телефона. После прохождения через набора различных стратегий вида они наконец совершают нападки на очень изящном решении: они просто создали немного массива и рассматривали смещение в битовый массив как номер телефона. Они тогда развернулись через их базу данных с единственной передачей, изменив бит для каждого числа к 1. После этого они развернулись через битовый массив однажды, выложив номера телефона для записей, которые имели набор битов высоко.

Вдоль тех строк, я полагаю, что можно использовать данные в самом массиве как структура метаданных для поиска дубликатов. Худший случай, у Вас мог быть отдельный массив, но я вполне уверен, можно использовать входной массив, если Вы не возражаете против небольшого количества свопинга.

я собираюсь не учесть n параметр в течение времени, будучи, b/c, который просто путает вещи - добавляющий в индексном смещении, довольно легко сделать.

Рассмотрите:

for i = 0 to m
  if (a[a[i]]==a[i]) return false; // we have a duplicate
  while (a[a[i]] > a[i]) swapArrayIndexes(a[i], i)
  sum = sum + a[i]
next

if sum = (n+m-1)*m return true else return false

Это не O (n) - вероятно, ближе к O (n Журнал n) - но это действительно предусматривает постоянное пространство и может обеспечить различный вектор нападения для проблемы.

, Если мы хотим O (n), затем с помощью массива байтов и некоторых битовых операций предоставит проверке дублирования дополнительные n/32 байты используемой памяти (принятие 32 битов ints, конечно).

РЕДАКТИРОВАНИЕ: вышеупомянутый алгоритм мог быть улучшен далее путем добавления, что сумма проверяет к внутренней части цикла и проверяет на:

if sum > (n+m-1)*m return false

тот путь это перестанет работать быстро.

1
ответ дан 3 revs 26 November 2019 в 21:31
поделиться

Принятие Вас знает только длину массива, и Вам разрешают изменить массив, это может быть сделано в O (1) пространство и O (n) время.

процесс имеет два простых шага. 1. "вид по модулю" массив. [5,3,2,4] => [4,5,2,3] (O (2n)) 2. Проверьте, что сосед каждого значения один выше, чем себя (по модулю) (O (n))

, Все сказали, что Вам нужно самое большее 3, проходит через массив.

вид по модулю является 'хитрой' частью, но цель проста. Примите каждое значение в массиве и сохраните его в его собственном адресе (длина по модулю). Это требует одной передачи через массив, цикличное выполнение по каждому местоположению, 'выселяющему' его значение путем свопинга его к его корректному местоположению и перемещения в значение в его месте назначения. Если Вы когда-нибудь перемещаетесь в значение, которое является конгруэнтным значению, которое Вы просто выселили, Вы имеете дубликат и можете выйти рано. Худший случай, это - O (2n).

проверка является единственной передачей через массив, исследующий каждое значение с, он - затем самый высокий сосед. Всегда O (n).

Объединенный алгоритм является O (n) +O (2n) = O (3n) = O (n)

Псевдокод из моего решения:

foreach(values[]) 
  while(values[i] not congruent to i)
    to-be-evicted = values[i]
    evict(values[i])   // swap to its 'proper' location
    if(values[i]%length == to-be-evicted%length)
      return false;  // a 'duplicate' arrived when we evicted that number
  end while
end foreach
foreach(values[])
  if((values[i]+1)%length != values[i+1]%length)
    return false
end foreach

я включал подтверждение концепции кода Java ниже, это не симпатично, но это передает все модульные тесты, которые я сделал для него. Я называю их 'StraightArray', потому что они соответствуют покерной комбинации прямого (непрерывный костюм для игнорирования последовательности).

public class StraightArray {    
    static int evict(int[] a, int i) {
        int t = a[i];
        a[i] = a[t%a.length];
        a[t%a.length] = t;
        return t;
    }
    static boolean isStraight(int[] values) {
        for(int i = 0; i < values.length; i++) {
            while(values[i]%values.length != i) {
                int evicted = evict(values, i);
                if(evicted%values.length == values[i]%values.length) {
                    return false;
                }
            }
        }
        for(int i = 0; i < values.length-1; i++) {
            int n = (values[i]%values.length)+1;
            int m = values[(i+1)]%values.length;
            if(n != m) {
                return false;
            }
        }
        return true;
    }
}
1
ответ дан 2 revs, 2 users 81% 26 November 2019 в 21:31
поделиться

МОЙ ТЕКУЩИЙ НАИЛУЧШИЙ ВАРИАНТ

def uniqueSet( array )
  check_index = 0; 
  check_value = 0; 
  min = array[0];
  array.each_with_index{ |value,index|
         check_index = check_index ^ ( 1 << index );
         check_value = check_value ^ ( 1 << value );
         min = value if value < min
  } 
  check_index =  check_index  << min;
  return check_index == check_value; 
end

O (n) и Пространство O (1)

я записал сценарий в комбинации грубой силы, которые могли привести это к сбою, и это не нашло никого. Если у Вас есть массив, который нарушает эту функцию, действительно говорят.:)

<час>

@J.F. Sebastian

не истинный алгоритм хеширования. Технически, это - высокоэффективный упакованный булев массив "замеченных" значений.

ci = 0, cv = 0
[5,4,3]{ 
  i = 0 
  v = 5 
  1 << 0 == 000001
  1 << 5 == 100000
  0 ^ 000001  = 000001
  0 ^ 100000  = 100000

  i = 1
  v = 4 
  1 << 1 == 000010
  1 << 4 == 010000
  000001 ^ 000010  = 000011
  100000 ^ 010000  = 110000 

  i = 2
  v = 3 
  1 << 2 == 000100
  1 << 3 == 001000
  000011 ^ 000100  = 000111
  110000 ^ 001000  = 111000 
}
min = 3 
000111 << 3 == 111000
111000 === 111000

точка этого являющегося главным образом, что для "фальсифицирования" больше всего проблемы случается, каждый использует дубликаты, чтобы сделать так. В этой системе XOR штрафует Вас за использование того же значения дважды и предполагает, что Вы вместо этого сделали это 0 раз.

протесты, здесь являющиеся, конечно:

  1. и длина входного массива и максимальное значение массива ограничены максимальным значением для $x в ( 1 << $x > 0 )
  2. , окончательная эффективность зависит от того, как Ваша базовая система реализует способности к:

    1. сдвиг 1 бит n помещает право.
    2. регистры xor 2. (где май 'регистров', в зависимости от реализации, охватите несколько регистров)

    редактирование Отмеченный, выше операторов кажутся сбивающими с толку. Принятие идеальной машины, где "целое число" является регистром с точностью Бога, которая может все еще выполнить ^ b в O (1) время.

, Но приводящий эти предположения к сбою, нужно начать спрашивать алгоритмическую сложность простой математики.

  • , Насколько сложный 1 == 1?, конечно, это должно быть O (1) каждый раз право?.
  • Что относительно 2^32 == 2^32.
  • O (1)? 2^33 == 2^33? Теперь у Вас есть вопрос размера регистра и конкретной реализации.
  • , К счастью, XOR и == может быть сделан параллельно, поэтому если Вы принимаете бесконечную точность и машину, разработанную для преодоления бесконечной точности, безопасно предположить, что XOR и == занимают время независимо от их значения (потому что его бесконечная ширина, это будет иметь бесконечные 0 дополнений. Очевидно, это не существует. Но также и, изменение 000000 к 000100 не увеличивает использование памяти.
  • все же на некоторых машинах, (1 < < 32) < < 1 будет использовать больше памяти, но сколько сомнительно.
0
ответ дан 10 revs 26 November 2019 в 21:31
поделиться

Путем работы с a[i] % a.length вместо a[i] Вы уменьшаете проблему до необходимости решить, что у Вас есть числа 0 к a.length - 1.

Мы считаем само собой разумеющимся это наблюдение и попытку проверить, содержит ли массив [0, m).

Находят первый узел, это не находится в его правильном положении, например,

0 1 2 3 7 5 6 8 4 ;     the original dataset (after the renaming we discussed)
        ^
        `---this is position 4 and the 7 shouldn't be here

Подкачка, что число в то, где это должно быть. т.е. подкачайте 7 с 8:

0 1 2 3 8 5 6 7 4 ; 
        |     `--------- 7 is in the right place.
        `--------------- this is now the 'current' position

Теперь мы повторяем это. При рассмотрении снова нашей текущей позиции мы спрашиваем:

"действительно ли это - корректное число для здесь?"

  • В противном случае мы подкачиваем его в его корректное место.
  • , Если это находится в правильном месте, мы перемещаем право и делаем это снова.

После этого правила снова, мы добираемся:

0 1 2 3 4 5 6 7 8 ;     4 and 8 were just swapped

Это будет постепенно создавать список правильно слева направо, и каждое число будет перемещено самое большее однажды, и следовательно это - O (n).

, Если существуют простофили, мы заметим его, как скоро существует попытка подкачать номер backwards в списке.

5
ответ дан 2 revs, 2 users 94% 26 November 2019 в 21:31
поделиться

Если Вы хотите знать сумму чисел [n ... n + m - 1] просто использование это уравнение.

var sum = m * (m + 2 * n - 1) / 2;

, Который работает на любое число, положительное или отрицательное, даже если n является десятичным числом.

0
ответ дан 2 revs 26 November 2019 в 21:31
поделиться

, Почему другие решения используют суммирование каждого значения? Я думаю, что это опасно, потому что, когда Вы добавляете вместе O (n) объекты в одно число, Вы технически используете больше, чем O (1) пространство.

O (1) указывает на постоянное пространство, которое не изменяется количеством n. Не имеет значения, если это - 1 или 2 переменные, пока это - постоянное число. Почему Вы говорите, что это - больше, чем O (1) пространство? При вычислении суммы n чисел путем накопления его во временной переменной Вы использовали бы точно 1 переменную так или иначе.

Комментарий в ответе, потому что система не позволяет мне писать комментарии все же.

Обновление (в ответ на комментарии): в этом ответе я имел в виду O (1) пространство везде, где "пространство" или "время" было опущено. Заключенный в кавычки текст является частью более раннего ответа, к которому это - ответ на.

0
ответ дан 2 revs 26 November 2019 в 21:31
поделиться

Учитывая это -

Запись метод, который берет международный массив из размера m...

я предполагаю, что справедливо прийти к заключению, что существует верхний предел для m, равного значению самого большого интервал (2^32 быть типичным). , Другими словами, даже при том, что m не определяется как интервал, то, что массив не может иметь дубликатов, подразумевает, что не может быть больше, чем количество значений, которые можно сформировать из 32 битов, который в свою очередь подразумевает, что m ограничен, чтобы быть интервалом также.

, Если такое заключение приемлемо, то я предлагаю использовать фиксированное пространство (2^33 + 2) * 4 байта = 34,359,738,376 байтов = 34.4 ГБ для обработки всех возможных случаев. (Не подсчет пространства, требуемого входным массивом и его циклом).

, Конечно, для оптимизации, я сначала принял бы m во внимание и выделил бы только фактическую необходимую сумму, (2m+2) * 4 байта.

, Если это приемлемо для O (1), пространственное ограничение - для установленной проблемы - тогда позволило мне продолжить двигаться к алгоритмическому предложению...:)

Предположения : массив m ints, положительный или отрицательный, ни одно большее, чем, что могут содержать 4 байта. Дубликаты обрабатываются. Первое значение может быть любым допустимым интервалом, Ограничивают m как выше.

Первый , создайте международный массив длины 2m-1, ary, и обеспечьте три международных переменные: уехал , разность , и право . Заметьте, что это делает 2m+2...

115-секундный , примите первое значение от входного массива и скопируйте его в положение m-1 в новом массиве. Инициализируйте эти три переменные.

  • устанавливает ary[m-1] - nthVal//, n=0
  • установил , уехал = разность = право = 0

Треть , цикл через остающиеся значения во входном массиве, и сделайте следующее для каждого повторения:

  • устанавливает разность = nthVal - ary[m-1]
  • если ( разность > m-1 + право || разность < 1-m + уехал ), возвращают false//за пределы
  • если ( ary [m-1 + разность ]! = пустой указатель), возвращают false//, дубликат
  • установил ary [m-1 + разность ] = nthVal
  • , если ( разность > уехала ) , уехал = , разность //ограничивает оставленный, связал дальнейшее право
  • если ( разность < право ) право = разность //ограничивает право, связанное дальнейший левый

, я решил поместить это в код, и это работало.

Вот рабочий образец с помощью C#:

public class Program
{
    static bool puzzle(int[] inAry)
    {
        var m = inAry.Count();
        var outAry = new int?[2 * m - 1];
        int diff = 0;
        int left = 0;
        int right = 0;
        outAry[m - 1] = inAry[0];
        for (var i = 1; i < m; i += 1)
        {
            diff = inAry[i] - inAry[0];
            if (diff > m - 1 + right || diff < 1 - m + left) return false;
            if (outAry[m - 1 + diff] != null) return false;
            outAry[m - 1 + diff] = inAry[i];
            if (diff > left) left = diff;
            if (diff < right) right = diff;
        }
        return true;
    }

    static void Main(string[] args)
    {
        var inAry = new int[3]{ 2, 3, 4 };
        Console.WriteLine(puzzle(inAry));
        inAry = new int[13] { -3, 5, -1, -2, 9, 8, 2, 3, 0, 6, 4, 7, 1 };
        Console.WriteLine(puzzle(inAry));
        inAry = new int[3] { 21, 31, 41 };
        Console.WriteLine(puzzle(inAry));
        Console.ReadLine();
    }

}
0
ответ дан hurst 26 November 2019 в 21:31
поделиться

примечание : этот комментарий основан на оригинальном тексте вопроса (это было исправлено, с тех пор)

, Если вопрос поставлен точно , как записано выше (и это не просто опечатка) и для массива размера n функция должен возвратиться (Истинный/Ложный), если массив будет состоять из чисел 1... n+1,

... тогда, то ответ всегда будет ложью, потому что массив со всеми числами 1... n+1 будет иметь размер n+1 и не n. следовательно, на вопрос можно ответить в O (1).:)

0
ответ дан 3 revs, 2 users 67% 26 November 2019 в 21:31
поделиться

Контрпример для алгоритм XOR .

(не может отправить его как комментарий)

@popopome

Для a = {0, 2, 7, 5,} это возвращается true (означает, что a перестановка диапазона [0, 4)), но это должно возвратиться false в этом случае (a, очевидно, не перестановка [0, 4)).

Другой встречный пример: {0, 0, 1, 3, 5, 6, 6} - все значения находятся в диапазоне, но существуют дубликаты.

я мог неправильно реализовать идею popopome (или тесты), поэтому вот код:

bool isperm_popopome(int m; int a[m], int m, int  n)
{
  /** O(m) in time (single pass), O(1) in space,
      no restrictions on n,
      no overflow,
      a[] may be readonly
  */
  int even_xor = 0;
  int odd_xor  = 0;

  for (int i = 0; i < m; ++i)
    {
      if (a[i] % 2 == 0) // is even
        even_xor ^= a[i];
      else
        odd_xor ^= a[i];

      const int b = i + n;
      if (b % 2 == 0)    // is even
        even_xor ^= b;
      else
        odd_xor ^= b;
    }

  return (even_xor == 0) && (odd_xor == 0);
}
0
ответ дан 5 revs 26 November 2019 в 21:31
поделиться

Версия C псевдокод b3

(для предотвращения неверного истолкования псевдокода)

Встречный пример: {1, 1, 2, 4, 6, 7, 7}.

int pow_minus_one(int power)
{
  return (power % 2 == 0) ? 1 : -1;
}

int ceil_half(int n)
{
  return n / 2 + (n % 2);
}

bool isperm_b3_3(int m; int a[m], int m, int n)
{
  /**
     O(m) in time (single pass), O(1) in space,
     doesn't use n
     possible overflow in sum
     a[] may be readonly
   */
  int altsum = 0;
  int mina = INT_MAX;
  int maxa = INT_MIN;

  for (int i = 0; i < m; ++i)
    {
      const int v = a[i] - n + 1; // [n, n+m-1] -> [1, m] to deal with n=0
      if (mina > v)
        mina = v;
      if (maxa < v)
        maxa = v;

      altsum += pow_minus_one(v) * v;
    }
  return ((maxa-mina == m-1)
          and ((pow_minus_one(mina + m-1) * ceil_half(mina + m-1)
                - pow_minus_one(mina-1) * ceil_half(mina-1)) == altsum));
}
0
ответ дан 8 revs 26 November 2019 в 21:31
поделиться

В Python:

def ispermutation(iterable, m, n):
    """Whether iterable and the range [n, n+m) have the same elements.

       pre-condition: there are no duplicates in the iterable
    """ 
    for i, elem in enumerate(iterable):
        if not n <= elem < n+m:
            return False

    return i == m-1

print(ispermutation([1, 42], 2, 1)    == False)
print(ispermutation(range(10), 10, 0) == True)
print(ispermutation((2, 1, 3), 3, 1)  == True)
print(ispermutation((2, 1, 3), 3, 0)  == False)
print(ispermutation((2, 1, 3), 4, 1)  == False)
print(ispermutation((2, 1, 3), 2, 1)  == False)

Это - O (m) вовремя и O (1) в пространстве. Это делает не , принимают во внимание дубликаты.

Альтернативное решение:

def ispermutation(iterable, m, n): 
    """Same as above.

    pre-condition: assert(len(list(iterable)) == m)
    """
    return all(n <= elem < n+m for elem in iterable)
0
ответ дан 4 revs 26 November 2019 в 21:31
поделиться
def test(a, n, m):
    seen = [False] * m
    for x in a:
        if x < n or x >= n+m:
            return False
        if seen[x-n]:
            return False
        seen[x-n] = True
    return False not in seen

print test([2, 3, 1], 1, 3)
print test([1, 3, 1], 1, 3)
print test([1, 2, 4], 1, 3)

Примечание, что это только делает одну передачу через первый массив, не считая линейный поиск вовлеченным в not in.:)

я также, возможно, использовал python set, но я выбрал простое решение, где рабочие характеристики set нельзя рассмотреть.

Обновление: Smashery указал, что у меня был misparsed "постоянный объем памяти", и это решение на самом деле не решает проблему.

0
ответ дан 2 revs 26 November 2019 в 21:31
поделиться

Product of m consecutive numbers is divisible by m! [ m factorial ]


so in one pass you can compute the product of the m numbers, also compute m! and see if the product modulo m ! is zero at the end of the pass

I might be missing something but this is what comes to my mind ...

something like this in python

my_list1 = [9,5,8,7,6]

my_list2 = [3,5,4,7]

def consecutive(my_list):

count = 0
prod = fact = 1
for num in my_list:
    prod *= num
    count +=1 
    fact *= count
if not prod % fact: 
    return 1   
else:   
    return 0 

print consecutive(my_list1)

print consecutive(my_list2)


HotPotato ~$ python m_consecutive.py

1

0

0
ответ дан 26 November 2019 в 21:31
поделиться

Я предлагаю следующее:

Выберите конечный набор простых чисел P_1, P_2, ..., P_K и вычислить вхождения элементов во входной последовательности (минус минимум) по модулю каждого P_i. Образец допустимой последовательности известен.

Например, для последовательности из 17 элементов по модулю 2 у нас должен быть профиль: [9 8], по модулю 3: [6 6 5], по модулю 5: [4 4 3 3 3] и др.

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

S_i is an int array of size P_i, initially filled with 0, i=1..K
M is the length of the input sequence
Mn = INT_MAX
Mx = INT_MIN

for x in the input sequence:
  for i in 1..K: S_i[x % P_i]++  // count occurrences mod Pi
  Mn = min(Mn,x)  // update min
  Mx = max(Mx,x)  // and max

if Mx-Mn != M-1: return False  // Check bounds

for i in 1..K:
  // Check profile mod P_i
  Q = M / P_i
  R = M % P_i
  Check S_i[(Mn+j) % P_i] is Q+1 for j=0..R-1 and Q for j=R..P_i-1
  if this test fails, return False

return True
0
ответ дан 26 November 2019 в 21:31
поделиться

Любой непрерывный массив [n, n + 1, ..., n + m-1] может быть отображен на «базовый» интервал [0, 1, ..., m ] с помощью оператора по модулю. Для каждого i в интервале существует ровно один i% m в базовом интервале и наоборот.

Любой непрерывный массив также имеет «интервал» m (максимум - минимум + 1), равный его размеру.

Используя эти факты, вы можете создать "обнаруженный" логический массив того же размера, содержащий изначально все ложные данные, и при посещении входного массива установить для связанных "обнаруженных" элементов значение true.

Этот алгоритм составляет O (n) в пространстве , O (n) вовремя и проверяет наличие дубликатов.

def contiguous( values )
    #initialization
    encountered = Array.new( values.size, false )
    min, max = nil, nil
    visited = 0

    values.each do |v|

        index = v % encountered.size

        if( encountered[ index ] )
            return "duplicates"; 
        end

        encountered[ index ] = true
        min = v if min == nil or v < min
        max = v if max == nil or v > max 
        visited += 1
    end

    if ( max - min + 1 != values.size ) or visited != values.size
        return "hole"
    else
        return "contiguous"
    end

end

tests = [ 
[ false, [ 2,4,5,6 ] ], 
[ false, [ 10,11,13,14 ] ] , 
[ true , [ 20,21,22,23 ] ] , 
[ true , [ 19,20,21,22,23 ] ] ,
[ true , [ 20,21,22,23,24 ] ] ,
[ false, [ 20,21,22,23,24+5 ] ] ,
[ false, [ 2,2,3,4,5 ] ]
]

tests.each do |t|
    result = contiguous( t[1] )
    if( t[0] != ( result == "contiguous" ) )
        puts "Failed Test : " + t[1].to_s + " returned " + result
    end
end
0
ответ дан 26 November 2019 в 21:31
поделиться

Мне нравится идея Грега Хьюджилла о сортировке по Radix. Чтобы найти дубликаты, вы можете выполнить сортировку за время O (N) с учетом ограничений на значения в этом массиве.

Для свободного пространства O (1) O (N) времени, которое восстанавливает исходный порядок в списке, вам не нужно делать фактическую замену этого числа; вы можете просто пометить его флагом:

//Java: assumes all numbers in arr > 1
boolean checkArrayConsecutiveRange(int[] arr) {

// find min/max
int min = arr[0]; int max = arr[0]
for (int i=1; i<arr.length; i++) {
    min = (arr[i] < min ? arr[i] : min);
    max = (arr[i] > max ? arr[i] : max);
}
if (max-min != arr.length) return false;

// flag and check
boolean ret = true;
for (int i=0; i<arr.length; i++) {
    int targetI = Math.abs(arr[i])-min;
    if (arr[targetI] < 0) {
        ret = false; 
        break;
    }
    arr[targetI] = -arr[targetI];
}
for (int i=0; i<arr.length; i++) {
    arr[i] = Math.abs(arr[i]);
}

return ret;
}

Хранение флагов внутри данного массива является своего рода обманом и не работает с распараллеливанием. Я все еще пытаюсь придумать способ сделать это, не касаясь массива за время O (N) и пространство O (log N). Проверка по сумме и по сумме наименьших квадратов (arr [i] - arr.length / 2.0) ^ 2 кажется, что это может сработать. Одна определяющая характеристика, которую мы знаем о массиве 0 ... m без дубликатов, заключается в том, что он равномерно распределен; мы должны просто проверить это.

Если бы я только мог это доказать.

Я хотел бы отметить, что вышеприведенное решение с использованием факториала занимает O (N) пространства для хранения самого факториала. N! > 2 ^ N, для хранения которого требуется N байтов.

0
ответ дан 26 November 2019 в 21:31
поделиться
Fail := False;
Sum1 := 0;
Sum2 := 0;
TSum1 := 0;
TSum2 := 0;

For i := 1 to m do
  Begin
    TSum1 := TSum1 + i;
    TSum2 := TSum2 + i * i;
    Item := Array[i] - n;
    If (Item < 0) or (Item >= m) then 
      Fail := True
    Else 
      Begin
        Sum1 := Sum1 + Item;
        Sum2 := Sum2 + Item * Item;
      End;
  End;
Fail := Fail Or (Sum1 <> TSum1) or (Sum2 <> TSum2);

Усталый и никакой компилятор, но я думаю, что это дает O (m) время выполнения и не может дурачиться.

-1
ответ дан Loren Pechtel 26 November 2019 в 21:31
поделиться

Кажется, что мы могли проверить на дубликаты путем умножения всех чисел n... n+m вместе, и затем сравнения того значения с ожидаемым продуктом последовательности без дубликатов м! / (n-1)! (отмечают, что это принимает, для последовательности невозможно пройти и ожидаемый тест суммы и ожидаемый тест продукта).

Настолько добавляющий к псевдокод hazzen , мы имеем:

is_range(int[] nums, int n, int m) {
  sum_to_m := (m * (m + 1)) / 2
  expected_sum := sum_to_m - (n * (n - 1)) / 2
  real_sum := sum(nums)
  expected_product := m! / (n - 1)!
  real_product := product(nums)
  return ((real_sum == expected_sum) && (expected_product == real_product))


РЕДАКТИРОВАНИЕ: Вот мое решение в Java с помощью Суммы квадратов для проверки на дубликаты. Это также обрабатывает любой диапазон (включая отрицательные числа) путем смещения последовательности для запуска по телефону 1.

// low must be less than high
public boolean isSequence(int[] nums, int low, int high) {
    int shift = 1 - low;
    low += shift;
    high += shift;

    int sum = 0;
    int sumSquares = 0;
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i] + shift;

        if (num < low)
            return false;
        else if (num > high)
            return false;

        sum += num;
        sumSquares += num * num;
    }

    int expectedSum = (high * (high + 1)) / 2;

    if (sum != expectedSum)
        return false;

    int expectedSumSquares = high * (high + 1) * (2 * high + 1) / 6;

    if (sumSquares != expectedSumSquares)
        return false;

    return true;
}
-1
ответ дан 3 revs 26 November 2019 в 21:31
поделиться

Как насчет того, чтобы использовать XOR с четными и нечетными числами отдельно. Думайте о разрядном уровне не само целочисленное значение.

bool is_same(const int* a, const int* b, int len)
{
    int even_xor = 0; 
    int odd_xor = 0;

    for(int i=0;i<len;++i)
    {
        if(a[i] & 0x01) odd_xor ^= a[i];
        else even_xor ^= a[i];

        if(b[i] & 0x01) odd_xor ^= b[i];
        else even_xor ^= b[i];
    }

    return (even_xor == 0) && (odd_xor == 0);
}
-1
ответ дан popopome 26 November 2019 в 21:31
поделиться

я не думаю, что объяснился в своем исходном сообщении хорошо (ниже сплошной линии). Для входа [1 2 3 4 5], например, алгоритм вычисляет сумму:

-1 + 2 - 3 + 4 - 5 

, который должен быть равен

-1^5 * ceil(5/2)

псевдокод ниже шоу, как проверяются векторы, которые не начинаются в 1. алгоритм обрабатывает случаи, где входной вектор не отсортирован, и/или это содержит дубликаты.

<час>

следующий алгоритм решает проблему путем вычисления переменных сумм векторных элементов:

-1 + 2 - 3 + 4 - 5 + .... + m = (-1)^m * ceil(m/2)

то, где перекрывают , окружает к самому близкому целому числу. Другими словами, нечетные числа вычтены из рабочих общих количеств, и четные числа добавляются к нему.

function test(data, m)
    altSum = 0
    n = Inf
    mCheck = -Inf
    for ii = 1:m
    {
        if data(ii) < n
            n = data(ii)
        if data(ii) > mCheck
            mCheck = data(ii)
        altSum = altSum + (-1)^data(ii) * data(ii)
    }
    if ((mCheck-n+1!=m) || (-1)^(n+m-1) * ceil((n+m-1)/2) - ((-1)^(n-1) * ceil((n-1)/2)) != altSum
        return false
    else
        return true
-1
ответ дан 5 revs 26 November 2019 в 21:31
поделиться

Линейный вовремя, постоянный в решении для пространства для int m

пространство Constant достигается путем использования знакового бита. Это может быть сделано для любого изменяемого int диапазон, если m [меньше чем 114] т.е. когда входной диапазон [n, n+m) может быть смещен к [1, m+1) диапазон, если n не положительно. На практике предварительное условие почти всегда верно, если введенный изменяемо.

/** gcc -std=c99 ... */
#include <assert.h>
#include <iso646.h>  // and, or
#include <limits.h>  // INT_MIN
#include <stdbool.h> // bool
#include <stdlib.h>  // abs()

bool inrange(int m; int a[m], int m, int n)
{
  /** Whether min(a[]) == n and max(a[]) == n+(m-1)
  */
  if (m == 0) return true; // empty range is a valid range

  // check out-of-range values
  int max = INT_MIN, min = INT_MAX;
  for (int i = 0; i < m; ++i) {
    if (min > a[i]) min = a[i];
    if (max < a[i]) max = a[i];
  }
  return (min == n and max == n+(m-1));
}

bool isperm_minus2(int m; int a[m], int m, int n)
{
  /** O(m) in time, O(1) in space (for 'typeof(m) == typeof(*a) == int')

      Whether a[] is a permutation of the range [n, n+m).

      feature: It marks visited items using a sign bit.
  */
  if (not inrange(a, m, n))
    return false; // out of range

  assert((INT_MIN - (INT_MIN - 1)) == 1); // check n == INT_MIN
  for (int *p = a; p != &a[m]; ++p) {
    *p -= (n - 1); // [n, n+m) -> [1, m+1)
    assert(*p > 0);
  }

  // determine: are there duplicates
  bool has_duplicates = false;
  for (int i = 0; i < m; ++i) {
    const int j = abs(a[i]) - 1;
    assert(j >= 0);
    assert(j < m);
    if (a[j] > 0)
      a[j] *= -1; // mark
    else { // already seen
      has_duplicates = true;
      break;
    }
  }

  // restore the array
  for (int *p = a; p != &a[m]; ++p) {
    if (*p < 0) 
      *p *= -1; // unmark
    // [1, m+1) -> [n, n+m)
    *p += (n - 1);        
  }

  return not has_duplicates; // no duplicates? (+ inrange)
}
-1
ответ дан 2 revs 26 November 2019 в 21:31
поделиться
Другие вопросы по тегам:

Похожие вопросы: