Сравните два целых массива и проверьте, имеют ли они равные значения

Question

Я хочу знать, что представляет собой лучший способ сравнить два несортированные массивы и проверить их, если они имеют равные значения с использованием C++? Я нашел решение в O (nlogn), но есть ли для этого решение O (n)? как, если да?

Пожалуйста, позвольте мне сказать вам, что это не университетский вопрос, мне нравится знать о решении проблемы ACM.

Спасибо.

Answer 1

Это зависит от того, какие ваши ценности и сколько памяти вы готовы потратить на это. В решении O (п) для массивов, содержащих уникальных целых чисел х в диапазоне 0 < = х < с, вы могли бы использовать вспомогательный массив char count[c] и сделать что-то вроде этого:

int array1[N]; 
int array2[N]; 

//get the values into array1 and 2 from somehwere 

char count[c]{0}; 
for(size_t i=0; i<N; i++) { 
    count[array1[i]]++; 
    count[array2[i]]++; 
} 

Теперь, два массивы будут равны тогда и только тогда, когда все элементы count равны 0 или 2. Это можно проверить в O (n), снова запустив тот же цикл, только на этот раз count[array1[i]] (и то же самое для array2) равным 2. Такая же методика может быть адаптирована для нескольких других сценариев: например, если значения не являются уникальными, вам нужно подсчитать в двух отдельных массивах, а затем проверить два значения для равенства. Однако, если количество возможных значений слишком велико, вам нужно прибегнуть к сохранению вашей информации («x содержится в массиве») в другой структуре, такой как дерево, где операции находятся в O (n log n), поэтому вы вернулись туда, где вы начали.