Функция, которая возвращает 0 или 1, если все элементы в диапазоне от 0 до n-1 существуют в массиве, время выполнения O (n)

Question

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

Я пытаюсь решить проблему в C, которая: Предположим, вы получили массив a и его размер NВы знаете, что все элементы в массиве находятся в диапазоне от 0 до n-1.Функция должна возвращать 0, если в диапазоне отсутствует число (от 0 до n-1).В противном случае возвращается 1. Как вы понимаете, возможны дубликаты.Дело в том, что он должен работать в режиме O (n).Я думаю, что мне удалось это сделать, но я не уверен.Глядя на старые посты здесь, это кажется почти невозможным, и алгоритм кажется намного более сложным, чем алгоритм, который я имею.Поэтому что-то не так со мной.Я не смог найти вход, который возвращает неправильный вывод, но вы.

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

int missingVal(int* a, int size)
{
  int i, zero = 0;
  for (i = 0; i < size; i++)
    //We multiply the element of corresponding index by -1
    a[abs(a[i])] *= -1;

  for (i = 0; i < size; i++)
  {
     //If the element inside the corresponding index is positive it means it never got multiplied by -1 
     //hence doesn't exist in the array
     if (a[i] > 0)
       return 0;

     //to handle the cases for zeros, we will count them
     if (a[i] == 0)
       zero++;
  }
  if (zero != 1)
    return 0;

  return 1;
}

Answer 1

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

Я предлагаю другое сопоставление: из[0, размер) до ( -1 - размер , -1 ], так что, например, {0, 1, 2, 3, 4, ...} становится {-1, -2, -3, -4, -5, ...}. Обратите внимание, что для представления целых чисел в виде дополнения до двух, INT_MIN = -INT_MAX - 1.

//  The following assumes that every value inside the array is in [0, size-1)
int missingVal(int* a, int size)      // OT: I find the name misleading
{
    int i = 0;
    for (; i < size; i++)
    {
        int *pos = a[i] < 0
            ? a + (-a[i] - 1)  // A value can already have been changed...
            : a + a[i];

        if ( *pos < 0 )        // but if the pointed one is negative, there's a duplicate
            break;

        *pos = -1 - *pos;
    }

    return i == size;         // Returns 1 if there are no duplicates 
}

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

if ( i != size ) {
    for (int j = 0; j < size; ++j) {
        if ( a[j] < 0 )
            a[j] = -a[j] - 1;
    }
} else {                             // I already know that ALL the values are changed
    for (int j = 0; j < size; ++j)
        a[j] = -a[j] - 1;
}

Answer 2

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

Answer 3

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

1. Все числа в массиве находятся между 0 и n-1
2. Размер массива n

Если в этом диапазоне отсутствует число, это может означать, что его место занял другой номер.Это означает, что массив должен иметь повторяющееся число

Алгоритм в O (n) времени и O (1) пространстве

1. Итерация по вашему массиву
2. Еслизнак текущего числа положительный, затем сделайте его отрицательным
3. Если вы нашли отрицательный знак, это означает, что у вас есть дубликат.Поскольку все элементы изначально больше (или равны), чем 0

Реализация

int missingVal(int arr[], int size)
{
    // Increment all the numbers to avoid an array with only 0s
    for (int i = 0; i < size; i++) arr[i]++;

    for (int i = 0; i < size; i++)
    {
        if (arr[abs(arr[i])] >= 0)
            arr[abs(arr[i])] = -arr[abs(arr[i])];
        else
            return 0;
    }

    return 1;
}

Редактировать

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

Хотя это добавляет еще один «проход» в алгоритм, решение - все еще в O (n)time & O (1) space

Edit # 2

Еще одно замечательное предложение от Bruno, которое оптимизирует это, - посмотреть, есть ли более одного нуля вместо увеличения массива.

Если их 2 или более, мы можем напрямую вернуть 0, поскольку мы нашли дубликат (и по тому же признаку, что не все числа в диапазоне находятся в массиве)

Answer 4

ваша программа работает, и она находится в O (N), но это довольно сложно, и наихудшее изменение исходного массива

может быть просто так:

int check(int* a, int size)
{
  int * b = calloc(size, sizeof(int));
  int i;

  for (i = 0; i != size; ++i) {
    b[a[i]] = 1;
  }

  for (i = 0; i != size; ++i) {
    if (b[i] == 0) {
      free(b);
      return 0;
    }
  }

  free(b);
  return 1;
}