C ++ Array пересечение - PullRequest
Новая
       62

C ++ Array пересечение

2 голосов
/ 01 июня 2011

Кто-нибудь знает, возможно ли превратить это из O (m * n) в O (m + n)? 

    vector<int> theFirst;
    vector<int> theSecond;
    vector<int> theMatch;

    theFirst.push_back( -2147483648 );
    theFirst.push_back(2);
    theFirst.push_back(44);
    theFirst.push_back(1);
    theFirst.push_back(22);
    theFirst.push_back(1);

    theSecond.push_back(1);
    theSecond.push_back( -2147483648 );
    theSecond.push_back(3);
    theSecond.push_back(44);
    theSecond.push_back(32);
    theSecond.push_back(1);

    for( int i = 0; i < theFirst.size(); i++ )
    {
        for( int x = 0; x < theSecond.size(); x++ )
        {
            if( theFirst[i] == theSecond[x] )
            {
                theMatch.push_back( theFirst[i] );
            }
        }
    }

Ответы [ 6 ]

5 голосов
/ 01 июня 2011

Поместите содержимое первого вектора в хеш-набор, например std::unordered_set.Это О (м).Сканируйте второй вектор, проверяя, есть ли значения в unordered_set, и ведите учет тех, которые есть.То есть n поисков хеш-структуры, поэтому O (n).Итак, O (m + n).Если у вас есть l элементов в перекрытии, вы можете рассчитывать O (l) для добавления их в третий вектор.std::unordered_set находится в черновике C ++ 0x и доступен в последних версиях gcc, также есть реализация в boost .

Отредактировано для использования unordered_set

Использование синтаксиса C ++ 2011: 

unordered_set<int> firstMap(theFirst.begin(), theFirst.end());

for (const int& i : theSecond) {
   if (firstMap.find(i)!=firstMap.end()) {
     cout << "Duplicate: " << i << endl;
     theMatch.push_back(i);
   }
}

Теперь остается вопрос: что вы хотите делать с дубликатами в оригиналах?Явно, сколько раз 1 должно быть в theMatch, 1, 2 или 4 раза?Это выводит: 

Duplicate: 1
Duplicate: -2147483648
Duplicate: 44
Duplicate: 1
2 голосов
/ 01 июня 2011

Используя это: http://www.cplusplus.com/reference/algorithm/set_intersection/

Вы должны быть в состоянии достичь O(mlogm + nlogn) Я считаю.(set_intersection требует, чтобы входные диапазоны уже были отсортированы).Однако это может работать немного иначе, чем ваше решение для дублирующих элементов.

0 голосов
/ 01 июня 2011

Я бы отсортировал более длинный массив O (n * log (n)), поиск элементов из более короткого массива O (m * log (n)).Итого тогда O (n * log (n) + m * log (n))

0 голосов
/ 01 июня 2011

Пожалуйста, поправьте меня, если я ошибаюсь, Вы предлагаете следующее решение проблемы пересечения: отсортировать два вектора и сохранить итерацию в обоих отсортированных векторах так, чтобы мы достигли общего элемента поэтому общая сложность будет (n * log (n) + m * log (m)) + (n + m) Предполагая k * log (k) как сложность сортировки

Я прав? Конечно, сложность будет зависеть от сложности сортировки.

0 голосов
/ 01 июня 2011

Если порядок элементов в результирующем массиве / наборе не имеет значения, тогда ответ - да.

Для произвольных типов элементов с некоторым определенным порядком лучший алгоритм - O( max(m,n)*log(min(m,n)) ). Для чисел ограниченного размера лучшим алгоритмом является O(m+n).

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

  • Выполните итерацию по большему массиву и проверьте, находится ли элемент внутри созданного ранее набора - для произвольного элемента двоичный поиск в порядке (что составляет O(log(min(n,m))), а для чисел единственная проверка - O (1).

0 голосов
/ 01 июня 2011

Предполагая, что вы хотите произвести theMatch из двух наборов данных, и вам нет дела до самих наборов данных, поместите один в unordered_map (доступно в настоящее время в Boost и указано в окончательном проекте комитета для C +).+11), отображая ключ в целое число, которое увеличивается при каждом добавлении и, следовательно, отслеживает количество раз, когда ключ встречается.Затем, когда вы получаете совпадение с другим набором данных, вы push_back получаете число совпадений, которое произошло в первый раз.

Вы можете перейти к O (n log n + m log m)сначала отсортировав векторы, либо O (n log n + m), создав std::map одного из них.

Предостережение: это не операции сохранения порядка, и theMatch выйдет вразные заказы с разными техниками.Мне кажется, что порядок считается произвольным.Если порядок, указанный в приведенном выше коде, необходим, я не думаю, что есть лучший алгоритм.

Редактировать:

Взять набор данных A и набор данных B типа Type.Создайте unordered_map<Type, int>.

Просмотрите набор данных A и проверьте каждого члена, чтобы увидеть, есть ли он на карте.Если нет, добавьте элемент с int 1 на карту.Если это так, увеличьте int.Каждая из этих операций в среднем равна O (1), поэтому этот шаг равен O (len A).

Просмотрите набор данных B и проверьте каждого члена, чтобы увидеть, находится ли он на карте.Если нет, переходите к следующему.Если это так, push_back участник в очередь назначения.int - это количество раз, когда это значение находится в наборе данных A, поэтому push_back - количество раз, когда член в A дублирует данное поведение.Каждая из этих операций в среднем равна O (1), поэтому этот шаг равен O (len B).

Это среднее поведение.Если вы всегда используете худший случай, вы вернетесь с O (m * n).Я не думаю, что есть способ гарантировать O (m + n).

...