我得到了這個挑戰。
const hierarchy = [
{ memberId: 1, parentMemberId: 8, level: 2, name: 'John Doe' },
{ memberId: 2, parentMemberId: 1, level: 3, name: 'Daniel Thorpe' },
{ memberId: 3, parentMemberId: 5, level: 3, name: 'David Suarez' },
{ memberId: 4, parentMemberId: 5, level: 3, name: 'Felix Mcgee' },
{ memberId: 5, parentMemberId: 8, level: 2, name: 'Deena Duarte' },
{ memberId: 6, parentMemberId: 3, level: 4, name: 'Ron Gaines' },
{ memberId: 7, parentMemberId: 9, level: 5, name: 'Kellie Clements' },
{ memberId: 8, parentMemberId: 0, level: 1, name: 'Tony Soprano' },
{ memberId: 9, parentMemberId: 3, level: 4, name: 'John Kavanagh' },
{ memberId: 10, parentMemberId: 8, level: 2, name: 'Shawn Huynh' },
];
使用這些資料,我應該逐級列印層次結構。結果示例:
Tony Soprano
John Doe -> Tony Soprano
Deena Duarte -> Tony Soprano
Shawn Huynh -> Tony Soprano
Daniel Thorpe -> John Doe -> Tony Soprano
我是這樣做的:
const printHierarchy = hierarchy => {
hierarchy.sort((memberA, memberB) => memberA.level - memberB.level);
const hierarchyObj = {};
for (let member of hierarchy) {
const { name, memberId, parentMemberId } = member;
hierarchyObj[memberId] = name;
if (hierarchyObj[parentMemberId] != undefined) {
hierarchyObj[memberId] = ` -> ${hierarchyObj[parentMemberId]}`;
}
}
for (let member of hierarchy) {
const { memberId } = member;
console.log(hierarchyObj[memberId]);
}
}
const hierarchy = [
{ memberId: 1, parentMemberId: 8, level: 2, name: 'John Doe' },
{ memberId: 2, parentMemberId: 1, level: 3, name: 'Daniel Thorpe' },
{ memberId: 3, parentMemberId: 5, level: 3, name: 'David Suarez' },
{ memberId: 4, parentMemberId: 5, level: 3, name: 'Felix Mcgee' },
{ memberId: 5, parentMemberId: 8, level: 2, name: 'Deena Duarte' },
{ memberId: 6, parentMemberId: 3, level: 4, name: 'Ron Gaines' },
{ memberId: 7, parentMemberId: 9, level: 5, name: 'Kellie Clements' },
{ memberId: 8, parentMemberId: 0, level: 1, name: 'Tony Soprano' },
{ memberId: 9, parentMemberId: 3, level: 4, name: 'John Kavanagh' },
{ memberId: 10, parentMemberId: 8, level: 2, name: 'Shawn Huynh' },
];
printHierarchy(hierarchy);
.as-console-wrapper { min-height: 100%!important; top: 0; }
經理說這很好用,但補充說:
“如果陣列包含 100,000 個元素,你還會使用迭代解決方案嗎?如果不是,你會怎么做?”
我真的找不到更好的方法。我錯過了什么?我們確實需要回圈排序。
uj5u.com熱心網友回復:
您可以構建一棵樹,然后列印該樹的所有名稱。
這種方法不需要排序資料。
const
getTree = (data, id, parent, children, root) => {
const t = {};
data.forEach(o => ((t[o[parent]] ??= {})[children] ??= []).push(Object.assign(t[o[id]] ??= {}, o)));
return t[root][children];
},
print = (parents = []) => ({ name, children = [] }) => {
const p = [name, ...parents];
console.log(p.join(' -> '));
children.forEach(print(p));
},
hierarchy = [{ memberId: 1, parentMemberId: 8, level: 2, name: 'John Doe' }, { memberId: 2, parentMemberId: 1, level: 3, name: 'Daniel Thorpe' }, { memberId: 3, parentMemberId: 5, level: 3, name: 'David Suarez' }, { memberId: 4, parentMemberId: 5, level: 3, name: 'Felix Mcgee' }, { memberId: 5, parentMemberId: 8, level: 2, name: 'Deena Duarte' }, { memberId: 6, parentMemberId: 3, level: 4, name: 'Ron Gaines' }, { memberId: 7, parentMemberId: 9, level: 5, name: 'Kellie Clements' }, { memberId: 8, parentMemberId: 0, level: 1, name: 'Tony Soprano' }, { memberId: 9, parentMemberId: 3, level: 4, name: 'John Kavanagh' }, { memberId: 10, parentMemberId: 8, level: 2, name: 'Shawn Huynh' }],
tree = getTree(hierarchy, 'memberId', 'parentMemberId', 'children', 0);
tree.forEach(print());
console.log(tree);
.as-console-wrapper { max-height: 100% !important; top: 0; }
uj5u.com熱心網友回復:
下一個提供的方法主要基于單個sort和一個map任務。
在第一個中間步驟中,將為基于成員專案創建Map基于查找。memberId
然后創建一個已排序的成員專案串列,該串列已經類似于最終成員優先級,因為它通過兩個屬性level(頂級類別)和memberId(第二級類別)比較和排序成員專案。
最后的mapping 任務將成員專案的排序串列(對于每個專案)迭代到基于字串的分層有序成員名稱圖中。它通過為每個專案聚合相關的分層成員名稱串列來實作這一點,同時查找總是下一個父成員,直到找不到父成員。
function getSortedListOfMemberHirarchyGraphs(memberList) {
// create a `memberId` based map of member items for looking it up.
const memberLookup = new Map(
memberList.map(item => [item.memberId, item])
);
return Array
// 1) compare and sort hierarchy levels descending.
// create shallow copy of `memberList` in order to not mutate it.
.from(memberList)
// - top level category: `level`
// - 2nd level category: `memberId`
.sort((a, b) => (a.level - b.level) || (a.memberId - b.memberId))
// 2) map sorted list of member items ...
.map(({parentMemberId, name}) => {
let nameList = [name];
let parentMember;
// 2a) ... while aggregating for each member's name ...
while (parentMember = memberLookup.get(parentMemberId)) {
parentMemberId = parentMember.parentMemberId;
// 2b) ... a list of related hierarchical member names ...
nameList.push(parentMember.name);
}
// 2c) ... into a graph of hierarchical member names.
return nameList.join(' => ');
});
}
const hierarchy = [
{ memberId: 1, parentMemberId: 8, level: 2, name: 'John Doe' },
{ memberId: 2, parentMemberId: 1, level: 3, name: 'Daniel Thorpe' },
{ memberId: 3, parentMemberId: 5, level: 3, name: 'David Suarez' },
{ memberId: 4, parentMemberId: 5, level: 3, name: 'Felix Mcgee' },
{ memberId: 5, parentMemberId: 8, level: 2, name: 'Deena Duarte' },
{ memberId: 6, parentMemberId: 3, level: 4, name: 'Ron Gaines' },
{ memberId: 7, parentMemberId: 9, level: 5, name: 'Kellie Clements' },
{ memberId: 8, parentMemberId: 0, level: 1, name: 'Tony Soprano' },
{ memberId: 9, parentMemberId: 3, level: 4, name: 'John Kavanagh' },
{ memberId: 10, parentMemberId: 8, level: 2, name: 'Shawn Huynh' },
];
console.log(
getSortedListOfMemberHirarchyGraphs(hierarchy)
);
console.log(
getSortedListOfMemberHirarchyGraphs(hierarchy)
.join('\n')
);
getSortedListOfMemberHirarchyGraphs(hierarchy)
.forEach(graph => console.log(graph));
.as-console-wrapper { min-height: 100%!important; top: 0; }
上面的實作再次沒有評論......
function getSortedListOfMemberHirarchyGraphs(memberList) {
const memberLookup = new Map(
memberList.map(item => [item.memberId, item])
);
return Array
.from(memberList)
.sort((a, b) => (a.level - b.level) || (a.memberId - b.memberId))
.map(({parentMemberId, name}) => {
let nameList = [name];
let parentMember;
while (parentMember = memberLookup.get(parentMemberId)) {
parentMemberId = parentMember.parentMemberId;
nameList.push(parentMember.name);
}
return nameList.join(' => ');
});
}
上述方法與下一個提供的第二次代碼重構不會映射兩次(創建查找并映射串列);相反,它直接reduce是分層排序的成員串列,它允許成員查找的編程聚合(創建成員項的名稱路徑所必需的聚合)。
function getSortedListOfMemberHirarchyGraphs(memberList) {
function collectMemberNameGraph(collector, item) {
const { memberLookup, result } = collector;
let { memberId, parentMemberId, name } = item;
memberLookup.set(memberId, item);
const nameList = [name];
let parentMember;
while (parentMember = memberLookup.get(parentMemberId)) {
parentMemberId = parentMember.parentMemberId;
nameList.push(parentMember.name);
}
result.push(nameList.join(' => '));
return collector;
}
return memberList
// skip creation of a shallow `memberList`
// copy and don't care about `sort` mutation.
.sort((a, b) => (a.level - b.level) || (a.memberId - b.memberId))
.reduce(collectMemberNameGraph, {
memberLookup: new Map,
result: [],
}).result;
}
const hierarchy = [
{ memberId: 1, parentMemberId: 8, level: 2, name: 'John Doe' },
{ memberId: 2, parentMemberId: 1, level: 3, name: 'Daniel Thorpe' },
{ memberId: 3, parentMemberId: 5, level: 3, name: 'David Suarez' },
{ memberId: 4, parentMemberId: 5, level: 3, name: 'Felix Mcgee' },
{ memberId: 5, parentMemberId: 8, level: 2, name: 'Deena Duarte' },
{ memberId: 6, parentMemberId: 3, level: 4, name: 'Ron Gaines' },
{ memberId: 7, parentMemberId: 9, level: 5, name: 'Kellie Clements' },
{ memberId: 8, parentMemberId: 0, level: 1, name: 'Tony Soprano' },
{ memberId: 9, parentMemberId: 3, level: 4, name: 'John Kavanagh' },
{ memberId: 10, parentMemberId: 8, level: 2, name: 'Shawn Huynh' },
];
console.log(
getSortedListOfMemberHirarchyGraphs(hierarchy)
);
console.log(
getSortedListOfMemberHirarchyGraphs(hierarchy)
.join('\n')
);
getSortedListOfMemberHirarchyGraphs(hierarchy)
.forEach(graph => console.log(graph));
.as-console-wrapper { min-height: 100%!important; top: 0; }
uj5u.com熱心網友回復:
這是一個完全產生所需輸出 OP 的解決方案。它建立在以下假設之上:
memberId陣列中每個物件的屬性hierarchy實際上是多余的,因為它直接對應index 1于陣列中物件的屬性,- a
parentMemberId==0表示該元素沒有父元素。
const h = hierarchy = [{ memberId: 1, parentMemberId: 8, level: 2, name: 'John Doe' }, { memberId: 2, parentMemberId: 1, level: 3, name: 'Daniel Thorpe' }, { memberId: 3, parentMemberId: 5, level: 3, name: 'David Suarez' }, { memberId: 4, parentMemberId: 5, level: 3, name: 'Felix Mcgee' }, { memberId: 5, parentMemberId: 8, level: 2, name: 'Deena Duarte' }, { memberId: 6, parentMemberId: 3, level: 4, name: 'Ron Gaines' }, { memberId: 7, parentMemberId: 9, level: 5, name: 'Kellie Clements' }, { memberId: 8, parentMemberId: 0, level: 1, name: 'Tony Soprano' }, { memberId: 9, parentMemberId: 3, level: 4, name: 'John Kavanagh' }, { memberId: 10, parentMemberId: 8, level: 2, name: 'Shawn Huynh' }];
function add2Array(el, arr = []) {
const [k, v] = Object.entries(el)[0];
arr.push(k)
if (typeof v == "object") add2Array(v, arr)
return arr
}
function ancestors(h) {
h.forEach(el => { if (el.parentMemberId) el.parent = h[el.parentMemberId - 1] })
h.forEach(el => {
el[el.name] = el.parent || "";
["memberId", "parentMemberId", "level", "name", "parent"].forEach(p => delete el[p]);
});
return h.map(e => add2Array(e)).sort((a, b) =>
a.length - b.length || a[0].localeCompare(b[0]));
}
const res = ancestors(hierarchy);
console.log(res.map(e =>e.join("->")).join("\n"));
.as-console-wrapper {
max-height: 100% !important;
top: 0;
}
uj5u.com熱心網友回復:
我會選擇將其分解一下。首先,我會將該平面串列轉換為一棵樹(或者實際上是一個森林,因為不能保證有一個根。)然后我會對結構進行廣度優先掃描,將節點及其祖先捕獲到一個大批。然后我的主要功能將提取名稱并反轉每個祖先,在節點之間添加箭頭。這是一個版本:
const nest = (xs, id = 0) => xs
.filter ((x) => x .parentMemberId == id)
.map (({memberId, parentMemberId, children = nest (xs, memberId), ...rest}) => ({
memberId, ...rest, ... (children .length ? {children} : {})
}))
const breadthFirst = (xs) =>
xs .length == 0 ? [] : [
... xs .map (x => [x]),
... xs .flatMap (x => breadthFirst (x .children || []) .map (ns => [x, ...ns]))
]
const display = (xs) =>
breadthFirst (nest (xs)) .map (xs => xs .map (x => x .name) .reverse () .join (' --> ')) .join ('\n')
const hierarchy = [{memberId: 1, parentMemberId: 8, level: 2, name: 'John Doe'}, {memberId: 2, parentMemberId: 1, level: 3, name: 'Daniel Thorpe'}, {memberId: 3, parentMemberId: 5, level: 3, name: 'David Suarez'}, {memberId: 4, parentMemberId: 5, level: 3, name: 'Felix Mcgee'}, {memberId: 5, parentMemberId: 8, level: 2, name: 'Deena Duarte'}, {memberId: 6, parentMemberId: 3, level: 4, name: 'Ron Gaines'}, {memberId: 7, parentMemberId: 9, level: 5, name: 'Kellie Clements'}, {memberId: 8, parentMemberId: 0, level: 1, name: 'Tony Soprano'}, {memberId: 9, parentMemberId: 3, level: 4, name: 'John Kavanagh'}, {memberId: 10, parentMemberId: 8, level: 2, name: 'Shawn Huynh'}]
console .log (display (hierarchy))
這里nest會將您的輸入變成如下內容:
[
{memberId: 8, level: 1, name: "Tony Soprano", children: [
{memberId: 1, level: 2, name: "John Doe", children: [
{memberId: 2, level: 3, name: "Daniel Thorpe"}
]},
{memberId: 5, level: 2, name: "Deena Duarte", children: [
{memberId: 3, level: 3, name: "David Suarez", children: [
{memberId: 6, level: 4, name: "Ron Gaines"},
{memberId: 9, level: 4, name: "John Kavanagh", children: [
{memberId: 7, level: 5, name: "Kellie Clements"}
]}
]},
{memberId: 4, level: 3, name: "Felix Mcgee"}
]},
{memberId: 10, level: 2, name: "Shawn Huynh"}
]}
]
然后一個非常通用的breadthFirst將其轉換為
[
[{name: "Tony Soprano", /* ... */}],
[{name: "Tony Soprano", /* ... */}, {name: "John Doe", /* ... */}],
[{name: "Tony Soprano", /* ... */}, {name: "Deena Duarte", /* ... */}],
[{name: "Tony Soprano", /* ... */}, {name: "Shawn Huynh", /* ... */}],
[{name: "Tony Soprano", /* ... */}, {name: "John Doe", /* ... */}, {name: "Daniel Thorpe", /* ... */}],
[{name: "Tony Soprano", /* ... */}, {name: "Deena Duarte", /* ... */}, {name: "David Suarez", /* ... */}],
[{name: "Tony Soprano", /* ... */}, {name: "Deena Duarte", /* ... */}, {name: "Felix Mcgee", /* ... */}],
[{name: "Tony Soprano", /* ... */}, {name: "Deena Duarte", /* ... */}, {name: "David Suarez", /* ... */}, {name: "Ron Gaines", /* ... */}],
[{name: "Tony Soprano", /* ... */}, {name: "Deena Duarte", /* ... */}, {name: "David Suarez", /* ... */}, {name: "John Kavanagh", /* ... */}],
[{name: "Tony Soprano", /* ... */}, {name: "Deena Duarte", /* ... */}, {name: "David Suarez", /* ... */}, {name: "John Kavanagh", /* ... */},{name: "Kellie Clements", /* ... */}]
]
最后,display只需將這些陣列轉換為簡單的箭頭分隔(反轉)的名稱串列。
nest可以改為在另一個答案forest中描述的更通用的函式之上構建,如下所示:
const forest = (build, isChild, root) => (xs) =>
xs .filter (x => isChild (root, x))
.map (node => build (node, root => forest (build, isChild, root) (xs)))
const nest = forest (
({memberId, parentMemberId, ...rest}, f) => ({memberId, parentMemberId, ...rest, children: f (memberId)}),
(id, x) => x .parentMemberId == id,
0
)
轉載請註明出處,本文鏈接:https://www.uj5u.com/yidong/476939.html
標籤:javascript 数组 算法 排序 映射
上一篇:按數字對數字進行排序
下一篇:散列和歸約到桶演算法
