Поиск элементов в диапазоне с использованием O (n) времени выполнения

Question

Я пытаюсь написать функцию, которая получает от пользователя массив размером «N» со значениями от 0 до> N-1, функция должна возвращать «1», если все значения от 0 до-> N-1, в противном случае он возвращает 0. мы можем предположить, что числа, которые будет вводить пользователь, являются только допустимыми значениями.между 0 ----> N-1.

Пример: N = 5, значения: 2,1,4,0,3 ----> возвращает 1, N = 5, значения: 2,3,4,0,3 ----> возвращает 0

Я пробовал разные способы решения этой проблемы.

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

МЫ МОЖЕМ ИСПОЛЬЗОВАТЬ SUBARRAY (другой массив счетчиков и т. Д.), И ФУНКЦИЯ ДОЛЖНА РАБОТАТЬ O (n).

Answer 1

Это моя версия.Он работает в O (n).

Идея состоит в том, чтобы манипулировать исходным массивом и добавлять к нему N, чтобы отметить все найденные значения.Затем мы выполняем проверку и проверяем, что все значения больше или равны N, и изменяем значение обратно на исходное.

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

#include <stdio.h>

int check(unsigned* a, size_t size) {
  for (size_t i = 0; i < size; ++i) {
    if (a[i] >= size) {
      return 0;
    }   
  }
  for (size_t i = 0; i < size; ++i) {
    size_t const x = a[i] % size;
    a[x] = x + size;
  }
  int result = 1;
  for (size_t i = 0; i < size; ++i) {
    if (a[i] < size) {
      result = 0;
    } else {
      a[i] = a[i] - size;
    }   
  }
  return result;
}


int main() {
  unsigned a1[] = {0,5,1,3,2,4};
  unsigned a2[] = {0,5,1,3,0,0};
  printf("a1: %d\n",check(a1,sizeof(a1)/sizeof(*a1)));
  printf("a2: %d\n",check(a2,sizeof(a2)/sizeof(*a2)));
}

Answer 2

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

Наблюдения:

1. Если массив был отсортированпроблема будет тривиальной.

2. Сортировка массива 0 ... N-1, где значения также 0 ... N-1, также тривиальна, поскольку позиция каждого элемента является егозначение, вы можете выполнить итерацию один раз, переставляя элементы в их окончательную позицию.

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

int check(unsigned* a, unsigned size) {
    for (unsigned i = 0; i < size; ++i) {
        unsigned b = a[i];
        if (b != i) {
            do {
                if (b < 0 || b >= size)
                    return false; // value out of range
                unsigned c = a[b];
                if (b == c)
                    return false; // duplicate value
                a[b] = b;
                b = c;
            } while (b != i);
            a[i] = i;
        }
    }
    return true;
}

Обратите внимание, что внутренний цикл придает решению вид O (N ² ), но это не так - каждый элемент посещается не более двух раз.Внутренний цикл необходим для разрешения циклов, как в {1,2,3,0}.

Answer 3

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

Итерация по массиву;для каждого элемента проверьте, является ли он отрицательным, если это так, отмените его и вычтите 1. Если он находится за пределами допустимого диапазона [0, N-1], конечно, входной массив недействителен, хотя вы говорите, что нам не нужно беспокоиться оэтот.

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

(«вычитать 1» нужно учитыватьдля 0, который остается тем же самым при отрицании)

Из-за принципа голубиного отверстия, если вы доберетесь до последнего элемента без дубликатов и без выходных значений, входной массив содержит все и только элементы в диапазоне[0, N-1].Если вам не нравится оставлять массив отрицательным, вы можете сделать последний проход, чтобы перевернуть знак каждого числа.

bool check(int *arr, int N) {
    bool ret = true;
    for(int i = 0; i < N && ret; ++i) {
        int v = arr[i];
        if(v < 0) v = -v - 1;
        if(v >= N || arr[v] < 0) ret = false;
        else arr[v] = -arr[v] - 1;
    }
    for(int i = 0; i < N; ++i) { 
        if(arr[i] < 0) arr[i] = -arr[i] - 1;
    } 
    return ret;
}