c# - Array.Sort / IComparable 有时在第一次调用时无法正确排序
问题描述
我正在尝试解决11321 - 排序!种类!!和排序!!!使用 C#,直接从 cpp 和 Java 翻译我的解决方案(以及其他人的)。
我的问题是在第一次通过时listName.Sort()
或者Array.Sort(listName, ...Comparer.Create()...)
没有正确地对输出进行排序。我必须调用它两次才能正确排序。
在某些情况下,我在调用 Array.Sort 时在 CompareTo() 中手动设置断点,故意在闭包内添加对列表的引用,以便在排序时观察值,并且在 Array.Sort 之后正确排序() 方法返回,然后我看到一些值返回到不正确的顺序。
我正在使用来自 uDebug 的 Morass 测试用例进行测试,我得到的一个不正确排序结果的示例位于输出的第 10919 行:
Accepted My Output
10919 457 10919 461
10920 461 10920 457
如您所见,数字 461 和 457 应按其模 500 值的升序排序,分别为 461 和 457。如果我在下面的代码中再次调用 sort 方法,那么我终于得到了正确的输出。
我想我的问题是,为什么会这样?我的实施有什么问题吗?我的实现几乎是接受的 Java 或 cpp 代码的一对一翻译。请注意,我也尝试过使用 LINQ 的 OrderBy(),它会产生不同的结果,但在调用足够多次时最终会产生正确的结果。
我有以下 Number 类和相应的 IComparable 实现:
class Number : IComparable<Number>
{
public int Value { get; }
public int Mod { get; }
public bool IsOdd { get; }
public Number(int val, int mod)
{
Value = val;
Mod = mod;
IsOdd = val % 2 != 0;
}
public int CompareTo(Number other)
{
var leftVal = Value;
var leftMod = Mod;
var rightVal = other.Value;
var rightMod = other.Mod;
var leftOdd = IsOdd;
var rightOdd = other.IsOdd;
if (leftMod < rightMod) return -1;
else if (leftMod > rightMod) return 1;
else
{
if (leftOdd && rightOdd)
{
return leftVal > rightVal ? -1 : 1;
}
else if (!leftOdd && !rightOdd)
{
return leftVal > rightVal ? 1 : -1;
}
else if (leftOdd)
{
return -1;
}
else// (rightOdd)
{
return 1;
}
}
}
}
我的主要方法:
public static void Main(string[] args)
{
while (true)
{
var settings = Console.ReadLine().Split(' ');
var N = int.Parse(settings[0]);
var M = int.Parse(settings[1]);
if (N == 0 && M == 0) break;
Console.WriteLine($"{N} {M}");
var output = new List<Number>();
var i = 0;
while (i < N)
{
var line = Console.ReadLine();
var val = int.Parse(line);
var mod = val % M;
output.Add(new Number(val, mod));
i++;
}
output.Sort();
// uncomment to produce acceptable answer
// output.Sort();
foreach (var line in output)
{
Console.WriteLine(line.Value);
}
}
Console.WriteLine("0 0");
}
编辑1:
请注意,我正在将标准输入和标准输出从文件重定向到 StringBuilder,因此我可以自动化测试。
static void Main(string[] args)
{
var builder = new StringBuilder();
var output = new StringWriter(builder);
Console.SetOut(output);
var solution = File.ReadAllText("P11321_Outputs");
var problem = new StreamReader("P11321_Inputs");
Console.SetIn(problem);
P11321_1.Main(args);
}
编辑2: 这是发生奇怪行为的测试用例的一部分。具体的重现步骤是,如果您将测试用例更改为只有 38 个项目,并从输入中删除 11 个,则 457 和 461 排序正确。
输入:
39 500
-121
582
163
457
-86
-296
740
220
-867
-333
-773
11
-446
-259
-238
782
461
756
-474
-21
-358
593
548
-962
-411
45
-604
-977
47
-561
-647
926
578
516
382
-508
-781
-322
712
0 0
输出:
39 500
-977
-474
-962
-446
-411
-867
-358
-333
-322
-296
-781
-773
-259
-238
-647
-121
-604
-86
-561
-21
-508
11
516
45
47
548
578
582
593
163
712
220
740
756
782
382
926
457
461
0 0
解决方案
您设法检查了布尔测试中的所有情况,除非值相等。排序算法不仅需要知道元素是否大于或小于彼此,还需要知道它们是否彼此相等。
if (leftMod < rightMod)
return -1;
else if (leftMod > rightMod)
return 1;
else
{
if (leftVal == rightVal)
{
return 0; // need this so you don't orphan an element when tested against itself
}
if (leftOdd && rightOdd)
{
return leftVal > rightVal ? -1 : 1;
}
else if (!leftOdd && !rightOdd)
{
return leftVal > rightVal ? 1 : -1;
}
else if (leftOdd)
{
return -1;
}
else// (rightOdd)
{
return 1;
}
}
推荐阅读
- ios - 在没有真实设备的情况下创建 iPhone 应用程序
- bots - 删除服务器中的所有频道
- c# - 尝试更改图片框中的图像时 C# Out of Memory
- formula - DAX 中的过滤器函数不允许对日期进行简单的数学运算
- arrays - 在 Rby 中以相反的顺序对数组进行排序
- node.js - 反应路由器将变量/状态传递给新路由?
- ios - keyboardWillChangeFrame 没有按预期工作
- javascript - Javascript cookie 添加 %5C
- c# - 如何处理 UWP、MVVM 的子列表中的 ItemClick 事件?
- python - Python 3.7 安装无法在 openSUSE Leap 42.3 上运行