在数组中查找对象的Javascript算法
在数组中查找对象的Javascript算法
提问于 2021-05-09 02:18:26
我有一个对象数组，其中包含有关项目的数据。每个项目都有一个ID和2个包含项目ID的数组，这将在之前和之后发生。如下所示：
let projects = [];
projects[0] = {
id: "ID_123",
before: [],
after: ["ID_523"],
}
projects[1] = {
id: "ID_523",
before: ["ID_123"],
after: ["ID_523","ID_827"],
}我希望找到所有相互依赖的项目，并将它们添加到同一个子组中。因此，我循环遍历数组，并从以前没有项目发生的项目开始。然后，我继续添加之后发生的第一个项目，将其添加到相同的子组中，并继续这样做，直到之后没有其他项目发生。我的算法是：
let subgroup = 0;
// loop through project array
for (let i=0; i<projects.length; i++) {
let next = projects[i]; // next contains the next project in the row
// find projects that have no projects happening before
if ((!next.hasOwnProperty('subgroup')) && (next.before.length == 0)) {
// do this as long as the next project has projects happening after
while (next.after.length > 0) {
// find the array-key of the first project happening afterwards
let key;
for (let n=0; n<projects.length; n++) {
if (projects[n].id == next.after[0]) {
key = n;
break;
}
}
// set the subgroup of the project with the key from above
projects[key].subgroup = subgroup;
// set the next project
next = projects[key];
}
subgroup++;
}
}不幸的是，算法并没有像预期的那样工作，一些项目根本不会得到分配的子组。我花了几天的时间寻找错误，但我找不到它。
希望有人能告诉我我哪里做错了。提前感谢！
回答 1
Stack Overflow用户
发布于 2021-05-09 06:10:15
您缺少连接，因为您的代码只查看after[0]，而不查看可能出现在after属性中的任何其他ID。更重要的是，您还应该通过before检查依赖关系，因为您可能会从不同的前辈到达一个项目，而这些项目应该都属于同一个子组。
您还可以避免为需要查找的每个ID迭代数据:而是创建一个Map，它将根据每个项目的ID为其设置关键字。
然后，为了确保处理after和before属性中的所有条目，执行广度优先搜索:将所有这些依赖项目添加到队列中，忽略已经访问过的项目(我将使用一个集合)：
let projects = [{
id: "ID_123",
before: [],
after: ["ID_523"],
}, {
id: "ID_523",
before: ["ID_123"],
after: ["ID_523","ID_827"],
}, {
id: "ID_827",
before: ["ID_523"],
after: [],
}, {
id: "ID_999",
before: [],
after: [],
}];
let subgroup = 0;
let map = new Map(projects.map(p => [p.id, p]));
for (let project of projects) {
if (project.before.length === 0 && !("subgroup" in project)) {
let todo = new Set([project]);
for (let project of todo) {
project.subgroup = subgroup;
for (let next of project.after) todo.add(map.get(next));
for (let prev of project.before) todo.add(map.get(prev));
}
subgroup++;
}
}
console.log(projects);
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/67450792
复制相关文章
相似问题
腾讯云开发者
