Эффективный алгоритм для сравнения и итерации двух больших массивов

Question

У меня есть эта проблема:

Я хочу повторить и сравнить каждый элемент array1 с каждым элементом array2, оба массива имеют одинаковую длину. Когда значения обоих элементов совпадают, я сохраняю значение j в моем массиве indexOfInterest [] для дальнейшего использования.

Этот код, который я использую, работает хорошо, но он чрезвычайно медленно сравнивает большие массивы (тысячи элементов), может кто-нибудь помочь мне реализовать эффективный алгоритм для этой задачи.

int i,j;

int counter = [array1 count];

int indexOfInterest[counter];


for (i = 0; i < counter; i++) {

    for (j = 0; j < counter; j++) {

        if ([[array1 objectAtIndex:i] intValue] == [[array2 objectAtIndex:j]intValue] ) {

            indexOfInterest[i] = j;
        }
    }
}

Answer 1

Вы можете хранить индексы array1 в хэш-карте (NSDictionary), где ключами являются элементы / значения, а значением является индекс этого элемента (или массив индексов, если элементам разрешено повторяться). Назовите его map_of_array1.

Затем выполните итерацию по array2 и найдите, если map_of_array1 [array2 [[i]] не равно нулю.

Таким образом, сложность времени будет O (n + m) вместоО (п * м).