Элегантный способ сравнения значений несортированных массивов в C?

Question

У меня есть два массива ints в C, и я бы хотел их сравнить. Это очень быстро, что я взломал вместе, но мне интересно, есть ли более быстрый способ.

1) Найдите целое число, которое не находится в массиве (arr2), который мы сравниваем.
2) Скопируйте этот исходный массив (arr2).
3) Итерацию через первый массив (arr1), и если элемент найден в скопированном массиве, мы заменяем значение в этом индексе значением, которое, как известно, не было в исходном массиве (это необходимо для предотвращения короткого замыкания когда в массиве находится несколько одинаковых значений).

#include <stdlib.h> 
#include <stdio.h> 
#include <time.h> 
#include <random.h> 


bool isin(int arr[], int elem, size_t len, size_t *index) { 
    int i; 
    for (i = 0; i < len; ++i) { 
     if (arr[i] == elem) { 
      if(index != NULL) 
       *index = i; 
      return true; 
     } 
    } 
    return false; 
} 

int notInArray(int arr[], size_t len) { 
    int r; 
    do { 
     r = rand(); 
    } while (isin(arr, r, len, NULL)); 
    return r; 
} 

bool arraysEqual(int arr1[], int arr2[], size_t len) { 
    size_t i, j, index; 
    int notInArr2 = notInArray(arr2, len); 

    int *arr = (int*)malloc(len * sizeof(int)); 

    for (i = 0; i < len; ++i) 
     arr[i] = arr2[i]; /*copy arr2 to arr*/ 

    for (i = 0; i < len; ++i) { 
     if (isin(arr, arr1[i], len, &index)) 
      arr[index] = notInArr2; /*replace that elemnt with something that we know is not in the original array*/ 
     else 
      return free(arr), false; 
    } 
    free(arr); 
    return true; 
} 

int main() { 
    srand(time(NULL)); 
    int a[] = { 3, 9, 1, 3, 8 }; 
    int b[] = { 1, 8, 3, 3, 9 }; 
    printf("%i\n", arraysEqual(a, b, sizeof(a)/sizeof(int))); 
    system("pause"); 
} 

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

Answer 1

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

Ваш предложенный алгоритм работает в O (n^2). Отвечая на ваш вопрос, да, есть способ сделать это в O (n logn) или даже O (n), если ваши целые числа не огромны. И это довольно простое упражнение, которое вы должны попробовать сделать сами.

Answer 2

С алгоритмической точки зрения, ваше решение не является оптимальным и выполняет сравнение в O(n^2) времени (потому что isin вызываются для каждого элемента в массиве) и O(n) дополнительного пространства (потому что вы выделяете копию массива).

Есть более дешевые способы выполнения этой задачи, вот краткое изложение 5 альтернативных подходов:

• вычислить HashSet или подсчитывать-словарь (распределение частот) одного массива и итерацию по сравнению с другими, чтобы определить подходящее значение -histograms (O(n) время, O(n) пространства)
• То же самое, что и выше, но использовать фильтр Блума, если вы не заботитесь для согласования частоты значений и не возражаете риск ложных срабатываний (O(n) времени, O(1) пространства)
• Сортировка 1 массивов на месте и использовать двоичный поиск для определения совпадений (O(n log n) время для Quicksort и O(log n) для двоичного поиска, O(1) пространства).
• Если входные массивы являются неизменными, а затем сделать то же самое, как выше вариант, но вроде в новый массив (то же время сложность, как описана выше, но O(n) пространства)
• Сортировать оба массив и проверить все элементы, в том же индексе равный (O(2n log n) время, O(1) площадь).

Answer 3

Вместо замены элемента, соответствующего случайному числу, не содержащемуся в массиве, я думаю, что у вас может быть массив булевых, который указал бы, что совпадение уже найдено. Тогда в вашем сравнении вы можете просто опустить эти элементы с соответствующим совпадением найденного значения true. Это избавило бы от необходимости искать значение не в массиве, и не было бы необходимости копировать arr2 в arr.