Алгоритм определения, содержит ли массив n ... n + m?

Question

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

Напишите метод, который принимает массив типа int размера m и возвращает (True / False), если массив состоит из чисел n ... n + m-1, всех чисел в этом диапазоне и только чисел в этом диапазоне , Массив не гарантируется для сортировки. (Например, {2,3,4} вернет true. {1,3,1} вернет false, {1,2,4} вернет false.

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

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

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

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

Answer 1

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

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

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

Ссылки:

• равномерное дискретное распределение
• дисперсия

Answer 2

В 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 (м) во времени и 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)

Answer 3

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

Answer 4

C версия Решение Кента Фредрика Ruby

(для облегчения тестирования)

Контрпример (для версии 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 (int) == 4, стандартное двоичное представление чисел).

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

Рубин: 1 << 100 # -> 1267650600228229401496703205376

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

В Ruby: check_index ^= 1 << i; эквивалентно check_index.setbit(i). Тот же эффект может быть реализован в 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);
    }
}

Answer 5

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) и не может быть обманутым.

Answer 6

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

Любой непрерывный массив также имеет размер 'span' 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

Answer 7

Произведение m последовательных чисел делится на m! [m factorial]

---

так что за один проход вы можете вычислить произведение чисел m, а также вычислить m! и посмотреть, если произведение по модулю м! ноль в конце прохода

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

как-то так в python

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

my_list2 = [3,5,4,7]

def подряд (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 

печать подряд (my_list1)

печать подряд (my_list2)

---

HotPotato ~ $ python m_consecutive.py

1

0

Answer 8

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

Постоянное пространство достигается за счет использования знакового бита. Это может быть сделано для любого изменяемого диапазона int, если m меньше INT_MAX, то есть, когда диапазон ввода [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)
}

Answer 9

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

Итак, добавив к псевдокоду Хаззена , мы получим:

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

Answer 10

Как насчет использования 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);
}