带有比较器的C#排序给出了不正确的结果

Question

class Solution {
List<List<int>> ans = new List<List<int>>();
public List<List<int>> subsets(List<int> A) {
var currList = new List<int>();
A.Sort();
GenerateSubSets(A, 0, currList);
ans.Sort(new ListComparer());
return ans;
}
public void GenerateSubSets(List<int> A, int position, List<int> currList)
{
if(position > A.Count-1)
{
ans.Add(currList);
return;
}

GenerateSubSets(A, position+1, new List<int>(currList));
currList.Add(A[position]);
GenerateSubSets(A, position+1, new List<int>(currList));
return; 
}
}
public class ListComparer : IComparer<List<int>>
{
public int Compare(List<int> list1, List<int> list2)
{
var list1Index = 0;
var list2Index = 0;
while((list1Index < list1.Count) && (list2Index < list2.Count))
{
if(list1[list1Index].CompareTo(list2[list2Index]) == 0)
{
list1Index++;
list2Index++;
continue;
}
return list1[list1Index].CompareTo(list2[list2Index]);
}
return list1.Count > list2.Count ? 1 : -1; 
}
}

运行测试用例时的上述代码

[8，5，19，11，10，7，18，16，13，17]

给了我错误的答案。

而不是得到

。。。[5 10 16 17][5 10 16 17 18]。。。

我得到

。。。[5 10 16 17 18][5 10 16 17]。。。

除了这一行，所有其他比较似乎都很好。此外，如果我调用排序函数两次，

ans.Sort(new ListComparer())

这个问题消失了。我错过了什么？我正在leetcode样式编辑器中运行此代码。

Answer 1

您似乎想要这样的东西：

public class ListComparer : IComparer<List<int>> {
public int Compare(List<int> left, List<int> right) {
// Compare with itself is always 0
if (ReferenceEquals(left, right)) 
return 0; 
// Let null be less than any list
if (left == null)
return -1;
if (right == null)
return 1;
// Compare corresponding items
for (int i = 0; i < Math.Min(left.Count, right.Count); ++i) {
int result = left[i].CompareTo(right[i]);
// items are not equal; we can return the result here
if (result != 0)
return result;
}

// All corresponding items are equal
// Let longer list be greater
return left.Count.CompareTo(right.Count); 
}
}

您可以推广解决方案(如果您想使用数组，而不是列表？long而不是int？)：

public sealed class SequenceComparer<T> : IComparer<IEnumerable<T>> 
where T : IComparable<T> {

public int Compare(IEnumerable<T>? left, IEnumerable<T>? right) {
if (ReferenceEquals(left, right))
return 0;
if (left is null)
return -1;
if (right is null)
return +1;
var comparer = Comparer<T>.Default;
using var leftEn = left.GetEnumerator();
using var rightEn = right.GetEnumerator();
while (true) {
if (leftEn.MoveNext())
if (rightEn.MoveNext()) {
int result = comparer.Compare(leftEn.Current, rightEn.Current);
if (result != 0)
return result;
}
else
return 1;
else if (rightEn.MoveNext())
return -1;
else
return 0;
}
}
}

Answer 2

这是我通常编写代码的方式

public class ListComparer : IComparer<List<int>>
{
public int Compare(List<int> list1, List<int> list2)
{
int min = Math.Min(list1.Count(), list2.Count());
for (int i = 0; i < min; i++)
{
if(list1[i] != list2[i])
return list1[i].CompareTo(list2[i]);
}
return list1.Count().CompareTo(list2.Count());
}
}