将两个列表合并为一个并对项目进行排序

Question

有没有办法合并(没有欺骗的联合)两个给定的列表,并使用ONE for循环以排序的方式存储项目？

另外,我正在寻找一种不使用API​​方法的解决方案(例如,union,sort等).

示例代码.

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:我在接受采访时被问过这个问题,但还没有找到答案.

Answer 1

如果没有在合并+排序操作之前对两个列表进行排序的前提条件,则无法在O(n)时间内执行此操作(或"使用一个循环").

添加该前提条件并且问题非常简单.

保留两个迭代器,每个列表一个.在每个循环中,比较每个列表中的元素并选择较小的元素.增加列表的迭代器.如果要在最终列表中插入的元素已经是该列表中的最后一个元素,请跳过插入.

在伪代码中:

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

Answer 2

你为什么不能使用api方法？重新发明轮子是愚蠢的.而且,这.ToList()就是杀死你的电话. 永远不要打电话.ToList()或.ToArray()直到你必须打电话,因为他们打破了懒惰的评价.

这样做,你会列出所需的最低金额:

var expectedResult = listOne.Union(listTwo).OrderBy(i => i);

这将使用hashset在一个循环中执行union,而惰性执行意味着sort的base-pass将依赖于union.但我不认为有可能在单次迭代中完成排序,因为排序不是O(n)操作.