这恰好是在 JavaScript 中,但这个问题也适用于其他语言。
我有一个很长的单词列表,按字母顺序排序,例如:
var myList= [
{word:"abstract", flavor:"old", extraData:...},
{word:"aircraft", flavor:"old", extraData:...},
{word:"airplane", flavor:"new", extraData:...},
{word:"banana", flavor:"old", extraData:...},
{word:"calories", flavor:"new", extraData:...},
...
];
我的目标是使用某种搜索方法(可能是二分搜索),以便找到有多少单词以给定的子字符串开头。在上面的示例中,给定子字符串“air” - 结果应为 2。
但是,有时我需要搜索整个列表,而其他时候我只需要搜索“旧”项目(根据上面的示例,结果应为 1)。
一个明显的解决方案是复制列表,例如:
var wholeList= [
{word:"abstract", flavor:"old", extraData:...},
{word:"aircraft", flavor:"old", extraData:...},
{word:"airplane", flavor:"new", extraData:...},
{word:"banana", flavor:"old", extraData:...},
{word:"calories", flavor:"new", extraData:...},
...
];
var oldList= [
{word:"abstract", flavor:"old", extraData:...},
{word:"aircraft", flavor:"old", extraData:...},
{word:"banana", flavor:"old", extraData:...},
...
];
这对于内存来说当然是非常浪费的。 对于此类问题还有其他/已知的解决方案吗?
最佳答案
要在单词之后进行过滤:
const search ="air";
const result = myList.filter(word => word.word.substr(0,search.length) === search);
只获取旧的:
const result = myList.filter( word => word.flavor === "old");
同时两者:
const search ="air", flavor = "old";
const result = myList.filter(word =>
word.flavor === flavor &&
word.word.substr(0,search.length) === search
);
为了改进这一点,可以使用嵌套映射作为查找树,或者可以将它们预先分组。不过,如果您搜索多次,那就值得了。
关于javascript - 在 2 种口味列表中进行二分搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46441621/