#c #arrays #tree #matching #similarity
#c #массивы #дерево #соответствие #сходство #c
Вопрос:
Допустим, у меня есть 2D-массив, который выглядит как:
________________
|10|15|14|20|30|
|14|10|73|71|55|
|73|30|42|84|74|
|14|74|XX|15|10|
----------------
Как я показал, столбцы не обязательно должны быть одинакового размера.
Теперь мне нужно найти наилучшее соответствие для каждого столбца (тот, в котором больше всего одинаковых элементов и меньше всего разных). Конечно, я мог бы сделать это за n ^ 2, но для меня это слишком медленно. Как я могу это сделать?
Я думал о дереве k-мерности и поиске ближайшего соседа для каждого из них, но я не знаю, хорошо ли это и будет ли работать так, как я хочу (вероятно, нет).
Результат, например:
- Первый столбец, скорее всего, третий (всего три разных — 10, 14, 42).
- Второй столбец -> пятый (только два разных — 15 и 55)
и так далее, и так далее … 🙂
Комментарии:
1. Я не понимаю вашего вопроса. В вашем примере говорится, что столбец 1 наиболее похож — почему? Кроме того, в столбце 1 нет 42, а в столбце 2 — 55.
2. В первом столбце есть элементы: 10, 14, 73, 14 В третьем столбце есть: 14, 73, 42 Теперь я не ищу большинство совпадающих элементов, я ищу наименее не совпадающие элементы. В этом случае у нас есть 14 в обоих (так что «удалите» их для последующего сравнения), 73 в обоих (так что снова «удалите»), и мы оставили только 3 элемента, которые находятся только на 1 стороне. Если мы сравним 1-й столбец с другими, мы обнаружим, что между ними осталось больше элементов 🙂 Также я думаю, что это можно сделать с помощью многомерного дерева и сравнить их расстояние (с некоторой работой, конечно), но я не так сильно «в деревьях» 🙂
Ответ №1:
Если вы знаете, что все числа в таблице состоят из 2 цифр (т. Е. 10 =< x <100), для каждого столбца создайте массив логических значений, где вы будете отмечать существующие числа:
bool array[5][100];
std::fill( amp;array[0][0], amp;array[0][0] sizeof(array) , false ); // init to false
for (int i = 0; i < 5; i )
{
for (int j = 0; j <5; j )
{
array[i][table[i][j]] = true;
}
}
Оттуда должно быть легко.