Найти количество общих элементов в заданных векторах из массива векторов

Question

Существует заданный массив векторов разного размера и общее количество элементов во всех векторах не будет превышать 10 . Каждый вектор содержит не менее 1 и не более 10 уникальных целых чисел, каждое целое число которых находится в диапазоне от 1 до 10 .

Будут 10 запросов, в которых каждый запрос запрашивает количество общих целых чисел в некоторых заданных векторах (не более 4).

Например: 4 векторов:

1 2 5 
3 5 6 
1 3 6 
6 7 

1 Запрос:

2 3 (vectors indexed 2 and 3) 

Ans:

2 (2 common integers {3,6}) 

Я не могу придумать эффективное решение для этой проблемы , Какой алгоритм/структура данных будет наиболее подходящим для этой проблемы? Любые ссылки были бы очень полезными.

EDIT: Нет целое число не будет происходить в более чем 4 векторов

Answer 1

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

Let v1, .., v4 обозначают четыре выбранных вектора.

Let i1=i2=i3=i4=0 
While (i1 < v1.length, i2 <v2.length, i3 < v3.length, i4 < v4.length) 
    Let X = max(v1[i1],v2[i2],v3[i3],v4[i4]) 
    Increase i1, i2, i3, i4 such that v1[i1]>=X, v2[i2]>=X, v3[i3]>=X, v4[i4]>=X 
    If v1[i1]=v2[i2]=v3[i3]=v4[i4] 
     count++ 
     i1++ 

Answer 2

Хранить векторы в структуре данных множества, что позволяет сделать поиск в O (1) и перебора всех элементов в O (N).

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