首先,对令人讨厌的标题表示歉意.我稍后会更正.
我有一些如下数据
“ BOULEVARD”,“ BOUL”,“ BOULV”,“ BLVD”
我需要一个O(1)的数据结构来查找其他单词.例如,如果我使用字典,则需要存储这样的键/值,这对我来说很奇怪,
abbr.Add("BLVD", new List<string> { "BOULEVARD","BOUL","BOULV", "BLVD" });abbr.Add("BOUL", new List<string> { "BOULEVARD", "BOUL", "BOULV", "BLVD" });abbr.Add("BOULV", new List<string> { "BOULEVARD", "BOUL", "BOULV", "BLVD" });abbr.Add("BOULEVARD", new List<string> { "BOULEVARD", "BOUL", "BOULV", "BLVD" });
使用哪种数据结构来使这些数据适合我的查询条件?
提前致谢
解决方法:
正如Petar Minchev所说,您可以将列表分为组列表和指向该组的键列表.为了简化此过程(使用),您可以编写自己的IDictionary实现并使用Add方法来构建这些组.我尝试了一下,它似乎起作用了.以下是实施的重要部分:
public class GroupedDictionary<T> : IDictionary<T,IList<T>>{ private Dictionary<T, int> _keys; private Dictionary<int, IList<T>> _valueGroups; public GroupedDictionary() { _keys = new Dictionary<T, int>(); _valueGroups = new Dictionary<int, IList<T>>(); } public void Add(KeyValuePair<T, IList<T>> item) { Add(item.Key, item.Value); } public void Add(T key, IList<T> value) { // look if some of the values already exist int existingGroupKey = -1; foreach (T v in value) { if (_keys.Keys.Contains(v)) { existingGroupKey = _keys[v]; break; } } if (existingGroupKey == -1) { // new group int newGroupKey = _valueGroups.Count; _valueGroups.Add(newGroupKey, new List<T>(value)); _valueGroups[newGroupKey].Add(key); foreach (T v in value) { _keys.Add(v, newGroupKey); } _keys.Add(key, newGroupKey); } else { // existing group _valueGroups[existingGroupKey].Add(key); // add items that are new foreach (T v in value) { if(!_valueGroups[existingGroupKey].Contains(v)) { _valueGroups[existingGroupKey].Add(v); } } // add new keys _keys.Add(key, existingGroupKey); foreach (T v in value) { if (!_keys.Keys.Contains(v)) { _keys.Add(v, existingGroupKey); } } } } public IList<T> this[T key] { get { return _valueGroups[_keys[key]]; } set { throw new NotImplementedException(); } }}
用法如下所示:
var groupedDictionary = new GroupedDictionary<string>();groupedDictionary.Add("BLVD", new List<string> {"BOUL", "BOULV"}); // after that three keys exist and one list of three itemsgroupedDictionary.Add("BOULEVARD", new List<string> {"BLVD"}); // now there is a fourth key and the key is added to the existing list instancevar items = groupedDictionary["BOULV"]; // will give you the list with four items
当然,实现整个接口需要大量工作,但是完成后,您将不必担心封装的类.
来源:https://www.icode9.com/content-1-542601.html联系客服