将两个列表合并为一个并对项目进行排序
有没有办法合并（没有欺骗的联合）两个给定的列表，并使用ONE for循环以排序的方式存储项目？
另外，我正在寻找一种不使用API方法的解决方案（例如，union，sort等）。
示例代码。
private static void MergeAndOrder() { var listOne = new List {3, 4, 1, 2, 7, 6, 9, 11}; var listTwo = new List {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：我在接受采访时被问过这个问题，但还没有找到答案。
如果没有在合并+排序操作之前对两个列表进行排序的前提条件，则无法在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
你为什么不能使用api方法？ 重新发明轮子是愚蠢的。 此外，它是.ToList()调用，它会杀了你。 永远不要调用.ToList()或.ToArray()直到你必须这样做，因为它们会破坏你的懒惰评估。
这样做，你会列出所需的最低金额：
var expectedResult = listOne.Union(listTwo).OrderBy(i => i);
这将使用hashset在一个循环中执行union，而惰性执行意味着sort的base-pass将依赖于union。 但我不认为有可能在单次迭代中完成排序，因为排序不是O（n）操作。
private static void MergeTwoSortedArray(int[] first, int[] second) { //throw new NotImplementedException(); int[] result = new int[first.Length + second.Length]; int i=0 , j=0 , k=0; while(i < first.Length && j
使用迭代器和流接口，任务并不复杂：
class MergeTwoSortedLists {static void Main（string [] args）{
var list1 = new List() { 1,3,5,9,11 }; var list2 = new List() { 2,5,6,11,15,17,19,29 }; foreach (var c in SortedAndMerged(list1.GetEnumerator(), list2.GetEnumerator())) { Console.Write(c+" "); } Console.ReadKey(); } private static IEnumerable SortedAndMerged(IEnumerator e1, IEnumerator e2) { e2.MoveNext(); e1.MoveNext(); do { while (e1.Current < e2.Current) { if (e1.Current != null) yield return e1.Current.Value; e1.MoveNext(); } if (e2.Current != null) yield return e2.Current.Value; e2.MoveNext(); } while (!(e1.Current == null && e2.Current == null)); } }
您可以编写一个合并和重复删除列表的循环，并使用二进制搜索方法将新值插入目标列表。
var listOne = new List { 3, 4, 1, 2, 7, 6, 9, 11 }; var listTwo = new List { 1, 7, 8, 3, 5, 10, 15, 12 }; var result = listOne.ToList(); foreach (var n in listTwo) { if (result.IndexOf(n) == -1) result.Add(n); }
我看到的最接近的解决方案是分配一个数组，知道整数是有界限的 。
int[] values = new int[ Integer.MAX ]; // initialize with 0 int size1 = list1.size(); int size2 = list2.size(); for( int pos = 0; pos < size1 + size2 ; pos++ ) { int val = pos > size1 ? list2[ pos-size1 ] : list1[ pos ] ; values[ val ]++; }
然后你可以争辩说你有一个“特殊”forms的排序数组:-)要获得一个干净的排序数组，你需要遍历values数组，跳过0计数的所有位置，并构建最终列表。
这只适用于整数列表，但很高兴这就是你所拥有的！
List sortedList = new List (); foreach (int x in listOne) { sortedList = x; } foreach (int x in listTwo) { sortedList = x; }
这是使用每个列表中的值作为存储值的索引位置。 任何重复值都将覆盖该索引位置的前一个条目。 它满足仅对值进行一次迭代的要求。
它当然意味着列表中将存在“空”位置。
我怀疑现在的职位已经填补了…… 🙂