c# - 检查字符串是否排序

Question

我有一个经过排序的简化字符串 "12345"。字符串可以包含数字 (0-9) 或字母 (a-z)。如果混合使用自然排序顺序。我需要一种方法来验证这是否属实。

尝试使用 linq 技术:

string items1 = "2349"; //sorted
string items2 = "2476"; //not sorted, 6<>7

bool sorted1 = Enumerable.SequenceEqual(items1.OrderBy(x => x), items1); //true
bool sorted2 = Enumerable.SequenceEqual(items2.OrderBy(x => x), items2); //false

但也可能有降序排序。

那有没有更好的办法

string items3 = "4321";
bool sorted3 = Enumerable.SequenceEqual(items3.OrderBy(x => x), items3) || Enumerable.SequenceEqual(items3.OrderByDescending(x => x), items3);

检查字符串是否排序？也许一些内置的解决方案？

Answer 1

您的解决方案非常好且可读性强。它的一个问题是它需要对 string which is O(n * log(n)) 进行排序，这可以通过迭代 string 而不对其进行排序来解决。

例如:

var firstDifs = items1.Zip(items1.Skip(1), (x, y) => y - x);

这个 Linq 将第一个 string 中的每 2 个项目投影到一个数字，表示它们的差异，所以如果你有 items1 = "1245" 输出将是:

firstDifs: {1, 2, 1}

现在您需要做的就是验证 firstDifs 是升序还是降序:

bool firstSorted = firstDifs.All(x => x > 0) || firstDifs.All(x => x < 0); //true

现在:

• Skip 是 O(1) 因为跳过 1 个单元格所需的操作量是常量。
• Zip 是 O(n)。
• All 是 O(n)。

所以整个解决方案是O(n)。

请注意，如果第一个 All 返回 false，则使用简单循环会更有效，因为第 3487 项更改了它方向(例如:1234567891)，第二个 All 将无故运行，而 Zip 也运行两次 _{(直到 All 需要)} - 因为 All 和 Linq< 有两次迭代 懒惰地计算它们。