Скажем, у нас был следующий набор вложенных массивов:
var array = [
[a,b,c],
[c,d,e],
[e,f,g],
[g,h,i]
]
Если мы начали с [a,b,c]
и хотели найти любой вложенный массив, который начинается с c
и, если они есть, нажмите элемент в индексе 2
этого массива на новый массив, который уже содержит c
, мы могли бы написать следующий код:
var container = [];
container.push(array[0][2]);
for (var i = 0; i < array.length; i++) if (array[0][2] === array[i][0]) container.push(array[i][2])
container
, следовательно, будет [c,e]
.
Достаточно просто.
Но что, если мы теперь также хотим проверить, соответствует ли e
другому array[i][0]
? И затем так далее и так далее, пока мы не проверим весь array
и не закончим со следующим массивом: [c,e,g,i]
.
То, что я пытаюсь сделать, - увидеть, соответствует ли последний элемент любого заданного массива первому элементу любого другого массива; и, если это произойдет, собрать последний элемент в этом массиве, а также проверить, соответствует ли этот элемент первому элементу любых других вложенных массивов.
Поэтому, если мы начнем с i
мы получим [i]
.
Если мы начнем с элемента g
мы получим [g,i]
.
Прямо сейчас я использую вложенные for
циклов и выражения if/else
:
for (var i = 0; i < array.length; i++) {
if (element === array[i][0]) {
container.push(array[i][2]);
for (var ii = 0; ii < array.length; ii++) {
if (array[i][2] === array[ii][0]) {
container.push(array[ii][2]);
for (var iii = 0; iii < array.length; iii++) {
if (array[ii][2] === array[iii][0]) {
container.push(array[iii][2])
for (var iiii = 0; iiii < array.length; iiii++) {
if (array[iii][2] === array[iiii][0]) {
container.push(array[iiii][2])
}
}
}
}
}
}
}
}
Нет ли более эффективного способа достичь этого?
Я должен был упомянуть, что исходный набор массивов может содержать такие повторяющиеся значения: [ [a,b,c], [a,b,c], [g,h,i], [x,y,z] ]
или [ [a,b,c], [a,b,c], [c,d,e], [x,y,z] ]
.
Для загрузки я заметил, что мой текущий подход будет выплевывать нежелательные результаты, такие как [c,e,c,e]
во втором случае выше, а не просто [c,e]
.
Было бы проще подумать об этом, используя вместо этого цифры:
var array = [
[2,n,4],
[4,n,6],
[6,n,8],
[8,n,10]
]
Если начальным значением было 4
, я бы затем нажал array[1][2]
или 6
в container
, а затем попытался сопоставить array[1][2]
или 6
с array[i][0]
. Таким образом, контейнер всегда будет представлять собой последовательности, такие как 2,4,6,8
или 6,8
или 4,6,8
и т.д.
Для записи это то, что означало @zerkms, создавая отдельный индекс, который представляет собой карту букв к письму:
var stringArray = [
['a', 'b', 'c'],
['c', 'd', 'e'],
['c', 'd', 'e'],
['e', 'f', 'g'],
['g', 'h', 'i']
];
var numberArray = [
[2, 3, 4],
[4, 5, 6],
[6, 7, 8],
[8, 9, 10]
];
// this implementation assumes there are no cycles or divergent branches
function chainSearch(array, start) {
var container = [start];
var map = new Map();
var index, inner, first, last;
var current = start;
// construct an element-to-element map in O(N)
for (index = 0; index < array.length; index++) {
inner = array[index];
first = inner[0];
last = inner[inner.length - 1];
if (!map.has(first)) {
map.set(first, last);
}
}
// assuming the chain is length L
// whole implementation is ~O(N+L) instead of O(N^L)
while (map.has(current)) {
current = map.get(current);
container.push(current);
}
return container;
}
console.log(chainSearch(stringArray, 'c').join());
console.log(chainSearch(stringArray, 'g').join());
console.log(chainSearch(numberArray, 2).join());
console.log(chainSearch(numberArray, 6).join());
Хорошая вещь об этой реализации заключается в том, что, хотя демо использует примитивы (строки и числа), это работает и для вложенных массивов не-примитивов, предполагая, что вы тестируете ссылки на одни и те же объекты, а не на идентичные копии.
Вы также можете попробовать такой подход:
function seq(source, result) {
if (source.length === 1)
return result.concat(source[0][source[0].length - 1]);
result = result || [];
if (source[0][source[0].length - 1] === source[1][0])
result = result.concat(source[1][0]);
return seq(source.slice(1), result);
}
console.log(seq(array));
for (var i = 1; i < array.length; i++) {
if (in_array(array[i][0], container)) { //if first element of current array matches any element in container
//add it to container if it not already there
if (!in_array(array[i][2], container)) {
container.push(array[i][2]);
}
//and then recheck all arrays to see if they match the new element
i = 1;
}
}
array
с container
а сравниваю array[a][2]
с array[z][0]
и если array[a][2] === array[z][0]
тогда я добавляю array[a][2]
и array[z][2]
с массивом container
, а затем сравните array[z][2]
с array[_][0]
для большего количества соответствий
для каждого массива, см., если какой-либо другой массив начинается с последнего значения массива, до или после
var container = [];
for (var i=0; i < ary.length; i++)
for (var j=0; j < ary.length; j++)
if (i != j && ary[i][2] == ary[j][0])
container.push(ary[j][0]);
Если вы смотрите только на более поздние подматрицы, просто запустите внутренний цикл при следующем индексе
var container = [];
for (var i=0; i < ary.length; i++)
for (var j=i+1; j < ary.length; j++)
if (i != j && ary[i][2] == ary[j][0])
container.push(ary[j][0]);
array[0][2]
или c
соответствует array[1][0]
или c
i, тогда необходимо сравнить array[1][2]
или e
с остальными массивами. Имеет ли это смысл?
new Map()
создает какой-то объект-прототип? я знаю, что методmap()
принимает 3 параметра / аргумента, но не похоже, что вы здесь используете? Я никогда не виделmap.has
(напоминает мне оhasOwnProperty
),map.set
илиmap.get
раньше.Map()
имеет ничего общего сArray.prototype.map()
. По сути, это хеш-таблица.