寻找最佳位置在列表元素 [英] Finding best position for element in list

问题描述

我有表的集合，填充在特定的顺序（要求是，这个顺序不能改变）。这个列表包含实体类型的对象。

列表的初始群体之后，我需要插入几个对象，这从另一个数据源的到来。这些对象需要在特定位置插入，以便排序是正确的。

例如，如果最初的列表中有以下元素

1. AAA
2. AAB
3. AAC
4. ACC
5. ADA

初​​始群体之后，我想插入ABB的元素，它需要进行3和4之间插入。

在那一刻我有以下发现新的元素正确的位置的方法。

 私有静态诠释FindPositionForArticle（串词）
    {
        字符串键= word.ToLower（）;
        对于（INT I = word.Length; I＆GT; = 0;我 - ）
        {
            如果（ⅰ＆其中; word.Length）
                键= key.Remove（I，1）;

            INT POS = 0;
            INT insertPos = 0;
            的foreach（在列表ArticleEntity文章）
            {
                如果（article.Text.ToLower（）。StartsWith（键））
                    insertPos = POS机;
                否则，如果（article.Text.ToLower（）StartsWith（键）及！＆功放; insertPos大于0）
                    返回insertPos ++;
                POS ++;
            }
        }
        返回0;
    }
 

此方法背后的宗旨理念：

1. 取字需要被插入，并试图找到元素的位置与名称相同的字

2. 如果什么也没有发现，从字删除最后一个字符并重新搜索。

3. 重复清除最后一个字符，直到最好的位置已被发现。

不幸的是我的方法有缺陷（不正确地实施）。目前，我的方法表明，最佳位置是0，这是完全不正确的。

如果你想用我的例子$ C $玩c您可以在这里下载：

http://dl.getdropbox.com/u/204110/FindPosition。 cs.txt

感谢你在前进。

解决方案

  INT指数= list.BinarySearch（字）;
 

如果指数为正或0时，该项目已在列表中找到。如果否定，它包含下一个最高的项目的列表中的索引的按位求补。

所以，对于这样的：

 名单，其中，串＆GT;名单=新的名单，其中，串＆GT; {AAA，AAB，AAC，ACC，反倾销协定};
INT指数= list.BinarySearch（ABB）; // =＆GT; -4
INT insertIndex =〜指数; // =＆GT; 3
list.Insert（insertIndexABB）;
 

I have List collection that is populated in specific order (the requirement is that, this order can not be changed). This list contains entity type objects.

After initial population of the list, I need to insert few more object, that are coming from another data source. These objects need to be inserted at specific position, so that sorting is correct.

For example if initial list has following elements

1. AAA
2. AAB
3. AAC
4. ACC
5. ADA

After initial population I want to insert "ABB" element, it need to be inserted between 3 and 4.

At moment I have following method of finding correct position for new elements.

    private static int FindPositionForArticle(string word)        
    {
        string key = word.ToLower();
        for (int i = word.Length; i >= 0; i--)
        {
            if(i < word.Length)
                key = key.Remove(i, 1);

            int pos = 0;
            int insertPos = 0;
            foreach(ArticleEntity article in list)
            {
                if(article.Text.ToLower().StartsWith(key))
                    insertPos = pos;
                else if (!article.Text.ToLower().StartsWith(key) && insertPos > 0)
                    return insertPos++;
                pos++;
            }
        }
        return 0;
    }

The purpose idea behind this method:

1. Take "word" that need to be inserted and try to find position of element with same name as "word"

2. If nothing has been found, remove last character from "word" and search again.

3. Repeat removal of last characters until best position has been found.

Unfortunately my methods has bugs(implemented incorrectly). Currently my methods suggests that best position would be 0, which is totally incorrect.

If You want to play with my example code You may download it at:

http://dl.getdropbox.com/u/204110/FindPosition.cs.txt

Thank You in advance.

解决方案

int index = list.BinarySearch(word);

If index is positive or zero, the item has been found in the list. If negative, it contains the bitwise complement of the index of the next highest item in the list.

So, for this:

List<string> list = new List<string>{"AAA","AAB","AAC","ACC","ADA"};
int index = list.BinarySearch("ABB"); // => -4
int insertIndex = ~index; // => 3
list.Insert(insertIndex, "ABB");

这篇关于寻找最佳位置在列表元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！