Под числами предположения меньше чем один не позволяется и нет никаких дубликатов, существуют простые идентификационные данные суммирования для этого - сумма чисел от 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), но если это не делает это должно быть решением исходный требуемый плакат.

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

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

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

Ссылки:

• универсальное дискретное распределение
• различие

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

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

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);
    }
}

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

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

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

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

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

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

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

Алгоритм любой-передачи требует Омеги (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.

Провалите меня, если я неправ, но я думаю, что мы можем определить, существуют ли дубликаты или не использование различия. Поскольку мы знаем среднее заранее (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, которые мы можем вычислить заранее.

Вот рабочее решение в 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. После этого они развернулись через битовый массив однажды, выложив номера телефона для записей, которые имели набор битов высоко.

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

я собираюсь не учесть 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

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

Принятие Вас знает только длину массива, и Вам разрешают изменить массив, это может быть сделано в 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;
    }
}

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

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 будет использовать больше памяти, но сколько сомнительно.

Путем работы с 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 в списке.

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

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

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

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

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

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

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

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

Запись метод, который берет международный массив из размера 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 в новом массиве. Инициализируйте эти три переменные.

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();
    }

}