检查字符串是否已排序

本文关键字：排序 是否 字符串 检查 | 更新日期: 2023-09-27 18:04:05

我有一个字符串，简化的"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);

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

检查字符串是否已排序

你的解决方案很好，很好读。它的一个问题是，它需要排序string 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 is O(n).
  • All is O(n).
<

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

注意使用一个简单的循环会更有效，同样，如果第一个All因为第3487项改变了它的方向(例如:1234567891)而返回了false，第二个All会毫无理由地运行，Zip也会运行两次(直到All需要的地方) -因为All和Linq有两次迭代惰性地计算它们

。

需要一个减速器。在c#中，它是Enumerable.Aggregate。这是O(n)算法

var query = "123abc".Aggregate(new { asceding = true, descending = true, prev = (char?)null }, 
(result, currentChar) =>
    new 
    { 
       asceding = result.prev == null || result.asceding && currentChar >= result.prev, 
       descending = result.prev == null || result.descending && currentChar <= result.prev, 
       prev = (char?)currentChar 
    }
);
Console.WriteLine(query.asceding || query.descending );

我曾经检查过与您的情况类似的东西，但使用的是巨大的数据流，所以性能很重要。我想出了这个小的扩展类，它执行得非常好:

public static bool IsOrdered<T>(this IEnumerable<T> enumerable) where T: IComparable<T>
{
    using (var enumerator = enumerable.GetEnumerator())
    {
        if (!enumerator.MoveNext())
            return true; //empty enumeration is ordered
        var left = enumerator.Current;
        int previousUnequalComparison = 0;
        while (enumerator.MoveNext())
        {
            var right = enumerator.Current;
            var currentComparison = left.CompareTo(right);
            if (currentComparison != 0)
            {
                if (previousUnequalComparison != 0
                    && currentComparison != previousUnequalComparison)
                    return false;
                previousUnequalComparison = currentComparison;
                left = right;
            }
        }
    }
    return true;
}

使用它显然很简单:

var items1 = "2349";
var items2 = "2476"; //not sorted, 6<>7
items1.IsOrdered(); //true
items2.IsOrdered(); //false

不需要比较所有的元素，你可以得到比公认的答案更好的答案:

var s = "2349"; 
var r = Enumerable.Range(1, s.Length - 1);
//var isAscending = r.All(i => s[i - 1] <= s[i]);
//var isDescending = r.All(i => s[i - 1] >= s[i]);
var isOrdered = r.All(i => s[i - 1] <= s[i]) || r.All(i => s[i - 1] >= s[i]);

var items = "4321";
var sortedItems = items.OrderBy(i => i); // Process the order once only
var sorted = sortedItems.SequenceEqual(items) || sortedItems.SequenceEqual(items.Reverse()); // Reverse using yield return

我会对所有元素进行简单迭代:

string str = "whatever123";
Func<char, char, bool> pred;
bool? asc = str.TakeWhile((q, i) => i < str.Length - 1)
               .Select((q, i) => str[i] == str[i+1] ? (bool?)null : str[i] < str[i+1])
               .FirstOrDefault(q => q.HasValue);
if (!asc.HasValue)
    return true; //all chars are the same
if (asc.Value)
    pred = (c1, c2) => c1 <= c2;
else
    pred = (c1, c2) => c1 >= c2;
for (int i = 0; i < str.Length - 1; ++i)
{
    if (!pred(str[i], str[i + 1]))
        return false;
}
return true;
相关文章：