Загадка интервью: массив size-n содержит числа из [i, i + n)

Question

Учитывая несортированный массив чисел, напишите функцию, которая возвращает true, если массив состоит из последовательных чисел.

Примеры:

1. Если массив равен {5, 2, 3, 1, 4}, то функция должна возвращать true, поскольку массив имеет последовательные числа от 1 до 5.

2. Если массив равен {83, 78, 80, 81, 79, 82}, то функция должна возвращать true, поскольку массив имеет последовательные числа от 78 до 83.

3. Если массив равен {34, 23, 52, 12, 3}, тофункция должна возвращать false, потому что элементы не являются последовательными.

4. Если массив равен {7, 6, 5, 5, 3, 4}, то функция должна возвращать false, потому что 5и 5 не являются последовательными.

Я придумал следующий алгоритм:

1. найти максимум и минимум массива

2. max-min + 1 должен быть размером массива

3. проверка на дубликаты

4. проверка для всех последовательныхоцепенелыймежду

Как мне достичь 4-го пути? (сложность должна быть O(n))

Другие предложения приветствуются.

Answer 1

Если входной массив A:

1. Найдите минимальное и максимальное значения A, верните False, если массив имеет неправильный размер.

2. Создать новый массив B того же размера, изначально со всеми нулями

3. Для каждого индекса i пусть B [A [i] - min] = 1.

4. Проверьте, содержит ли B все еще нули.

Каждый шаг занимает время O (n).

Answer 2

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

Определите минимальное и максимальное значения массива. Если (max - min + 1)! = N, вернуть false.

Вычтите минимум из каждого элемента в массиве. Теперь у нас есть массив с n элементами из диапазона [0, n). Теперь нам нужно просто проверить наличие дубликатов. Это можно сделать за линейное время (каждый элемент перемещается не более одного раза) с помощью кода, подобного следующему:

for (int i = 0; i != n; ++i)
{
    if (A[i] != i)
    {
        int temp = A[i];
        for (;;)
        {
            int index = temp;
            if (A[index] == index)
            {
                // We have a duplicate
                return false;
            }
            std::swap(temp, A[index]);
            if (index == i)
            {
                // A[i] now contains i
                break;
            }
        }
    }
}
// If we get to here, there are no duplicates

Answer 3

int visited[max - min + 1];

for(c = min; c <= max; c++) {
    visited[array[c] - min] += 1;

    if(visited[array] > 1)
        return false;               // since this is a duplicate
}

Все должно быть в порядке.visit [] отслеживает, сколько раз появилось число из исходного массива.Если какой-либо из его элементов больше двух, есть дубликат, поэтому верните false;Поскольку размер обоих массивов max-min + 1, в конце цикла посещение [] заполнено, потому что мы посетили все элементы массива [].Таким образом, посещение является пустым, где-то должен быть дубликат, но нам не нужно беспокоиться, потому что в то время мы все еще возвращаем false.

Answer 4

bool consecutive(int a[], size_t n)
{
    int min = find_min(a,n);
    int max = find_max(a,n);

    if (max - min + 1 == n) {
        // variant of counting sort, O(n)
        // note: never freed, don't use in production
        int *freq = calloc(sizeof(int), n);

        for (size_t i=0; i<n; i++)
            if (++freq[a[i] - min] > 1)
                return false;
        return true;
    }
    return false;
}

Answer 5

Найти минимальный элемент, максимальный элемент и сумму элементов в массиве.

Они образуют Arthematic Progression и сумма элементов равна: (no.Of of element / 2) * (2 * minElement + (n-1) * отличие)

разница составляет 1 в этом случае

если сумма == (array.length / 2) * (2 * minElement + (array.length-1) * 1) && maxElement == (minElement + (длина Array-1) * 1)

Тогда числа являются последовательными.

Нет дополнительной сложности пространства, а сложность времени равна O (n)

Спасибо, @jpalecek за исправление. Это должно быть хорошо сейчас

Answer 6

Вот кое-что, что работает для 1..N, вы можете просто использовать форумные арифметические ряды, чтобы приспособиться к этому [i, i + n]

// gcc -Wall q1.cc -o q1 && q1                                                                          

//Given an array of size N in which every number is between 1 and N, write a simple program to determine
//if there are any duplicates in it.                                                                    

//answer                                                                                                
/* The numbers can be assumed to not be stored in sorted order.  We also assume that all numbers are    
between 1 and N inclusive.  If for example they are not, then we will return true indicating that there 
is a possibility of a duplicate.                                                                        

This can be implemented using a bit array of size N all initialized to 0.  as we iterate the input array
of numbers, we simply check if the bit array at that number index is set, if so, we return true.  if not
we set the bit.  we loop until we get to the end of the list, and if we get there, that means no        
duplicate was found, and we can return false.                                                           

However, the above algorithm has the problem of using extra space.  A better idea is to take advantage  
of the fact that we are guaranteed that the numbers are between 1 and N.  if we were to use the fact    
that the arithmetic sum of these numbers is equal to n(n+1)/2, then we can just sum up all the numbers  
and ensure that it equals the above sum.  If it does, we have no duplicate, else we do.                 
*/                                                                                                      

#include <stdio.h>                                                                                      
#include <assert.h>                                                                                     

bool any_dup(const int *a, int n)                                                                       
{                                                                                                       
        int req_sum = n*(n+1)/2;                                                                        

        int s = 0;                                                                                      
        for (int i = 0;i<n;i++)                                                                         
                s += a[i];                                                                              

        return (s != req_sum);                                                                          
}                                                                                                       


int main()                                                                                              
{                                                                                                       
        int a[]={1,2,3,4,5};                                                                            
        assert(!any_dup(a,5));                                                                          

        int b[]={1,2,2,3,3,4,5,6};                                                                      
        assert(any_dup(b,8));                                                                           

        int c[]={5,2,3,1,4};                                                                            
        assert(!any_dup(c,5));                                                                          

        int d[]={34,21,1,4,2};                                                                          
        assert(any_dup(d,5));                                                                           

        return 0;                                                                                       
}                                                                                                       

Answer 7

Как вы и просили, 4-й шаг в вашем алгоритме вообще не нужен (поскольку # 2 и # 3 гарантируют, что они последовательны)

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

int is_consecutive(int *a, int size)  // O(n) algo
{   
 int min, max;
 hash H;
 if(!a || size == 0 ) return -1;
 max=min=a[0];
 H.insert(a[0]);

 for(i=1; i<size; i++) {
   if(H.find(a[i]) { delete H; return 0; }  // duplicacy check
   else H.insert(a[i]);
   if(a[i] < min) min = a[i];
   else if(a[i] > max) max = a[i];
 }
 if(size != (max - min)) { delete H; return 0; }  //range = size check
 delete H;   
 return 1;
}

Answer 8

Я не слишком хорош в C, но тебе нужно сделать шаг 4?Конечно, если 2 истинно и нет дубликатов, то оно содержит последовательность, иначе это не так?