合并两个列表成一个和排序的项目

问题描述

有没有办法合并（工会不愚弄）两个给定的名单成一个，使用一个for循环存储排序方式的项目？

Is there a way to merge(union without dupes) two given lists into one and store the items in sorted way by using ONE for loop?

另外，我要寻找一个解决方案，它并没有充分利用的API方法（如，工会，排序等）。

Also, i am looking for a solution which does not makes use of API methods ( like, union, sort etc).

示例代码。

private static void MergeAndOrder()
{
var listOne = new List<int> {3, 4, 1, 2, 7, 6, 9, 11};
var listTwo = new List<int> {1, 7, 8, 3, 5, 10, 15, 12};

//Without Using C# helper methods...
//ToDo.............................

//Using C# APi.
var expectedResult = listOne.Union(listTwo).ToList();
expectedResult.Sort();//Output: 1,2,3,4,5,6,7,8,9,10,11,12,15
//I need the same result without using API methods, and that too by iterating over items only once.


}

PS：我一直在问这个问题在接受采访时，也没有找到答案尚未。

PS: I have been asked this question in an interview, but couldn't find answer as yet.

推荐答案

如果没有先决条件，这两个列表是在合并之前进行排序+排序操作，你不能这样做在O（n）时间（或使用一个循环）。

Without the precondition that both lists are sorted before the merge + sort operation, you can't do this in O(n) time (or "using one loop").

添加一个前提，这个问题是很容易的。

Add that precondition and the problem is very easy.

请两个迭代，每个列表。在每个循环中，比较来自每个列表的元素，然后选择较小。增加该列表的迭代器。如果您是关于最终名单要插入的元素已经是最后一个元素在该列表中，跳过插入

Keep two iterators, one for each list. On each loop, compare the element from each list and choose the smaller. Increment that list's iterator. If the element you are about to insert in the final list is already the last element in that list, skip the insert.

在伪代码：

List a = { 1, 3, 5, 7, 9 }
List b = { 2, 4, 6, 8, 10 }
List result = { }
int i=0, j=0, lastIndex=0
while(i < a.length || j < b.length)
    // If we're done with a, just gobble up b (but don't add duplicates)
    if(i >= a.length)
        if(result[lastIndex] != b[j])
            result[++lastIndex] = b[j]
        j++
        continue

    // If we're done with b, just gobble up a (but don't add duplicates)
    if(j >= b.length)
        if(result[lastIndex] != a[i])
            result[++lastIndex] = a[i]
        i++
        continue

    int smallestVal

    // Choose the smaller of a or b
    if(a[i] < b[j])
        smallestVal = a[i++]
    else
        smallestVal = b[j++]

    // Don't insert duplicates
    if(result[lastIndex] != smallestVal)
        result[++lastIndex] = smallestVal
end while

这篇关于合并两个列表成一个和排序的项目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！