Как максимально эффективно сравнить два массива разной длины?

Question

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

bool value_check(int arr1[], int arr2[], int nums)
{
    int  value = 0;
    for(int i = 0; i < nums; i++)
    {
        value = arr1[i];
        for(int j = 0; j < nums; j++)
        {
            if (value == arr2[j])
            {
                return true;
            }
        }
    }
return false;
}

Answer 1

Как отмечает Калеб, асимптотически быстрее сначала сортировать входные данные.

Вот кое-что, что использует std::set_intersection и все же умело возвращается с нетерпением.

struct Found{};
struct Finder : std::iterator<std::output_iterator_tag, void, void, void, void> // for brevity
{
    Finder* operator->() { return this; }
    Finder& operator*() { return *this; }
    Finder& operator=(int) { throw Found{}; }
    Finder& operator++() { return *this; }
    Finder& operator++(int) { return *this; }
};

bool any_intersection(std::vector<int> lhs, std::vector<int> rhs)
{    
    std::sort(lhs.begin(), lhs.end());
    std::sort(rhs.begin(), rhs.end());
    try { std::set_intersection(lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), Finder{}); }
    catch (Found &) { return true; }
    return false;
}

Answer 2

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

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

Это можно сделать за O (n)

bool value_check(int arr1[], int arr2[], int nums)
{
std::unordered_map<int, int> first;

for (int i = 0; i < nums; i++)
{
    if (!first.count(arr1[i]))
        first[arr1[i]] = 1;
    else
        first[arr1[i]]++;
}

for (int i = 0; i < nums; i++)
{
    if (first.count(arr2[i]) > 0)
    { 
        return true;
    }
}
return false;
}

Answer 3

Как максимально эффективно сравнить два массива разной длины?

Обычно нужно отсортировать массивы. Как только это будет сделано, сравнение будет быстрым, потому что вы можете пройти по двум массивам вместе.

Сортировка массивов может быть выполнена за время O (n log (n)), а сравнение их после этого занимает только O (n) время, поэтому в целом вы получаете сложность O (n log (n)).