快速比较相同字符串数组的元素

Question

EDIT ：我认为网站上的 C# 编译器或其他东西有问题，我不知道如何才能比最终获得项目更快。我切换到 Java 并且它工作正常，与 C# 项目的逻辑完全相同。

using System;

namespace ConsoleApp1
{
class Program
{
    static void Main(string[] args)
    {
        int testCases = int.Parse(Console.ReadLine());
        while (testCases > 0)
        {
            int nNum = int.Parse(Console.ReadLine()); //Needed num version for validation
            string[] numbers = new string[nNum];
            for (int j = 0; j < numbers.Length; j++)               
                numbers[j] = Console.ReadLine(); //This fills array with numbers                
            Array.Sort(numbers); //Sorts string array
            bool consistent = true; //Checking whether we detect any 'inconsistencies'
            for (int j = 0; j < numbers.Length - 1; j++)
            {
                if (numbers[j+1].StartsWith(numbers[j]))
                {
                    consistent = false;
                    break;
                }
                
            }
            Console.WriteLine(consistent ? "YES" : "NO");
            testCases--;
        }

    }
}
}

这是我的 C# 最终代码。无论我做什么，它都持续超过 3 秒。

原始问题：我会尽快解决这个问题——我的任务是获取 1-10000 个唯一的 phone 数字。我必须检查数组中的数字是否是另一个数字的前缀，即“911”是一个 phone 数字，而“911859285”是另一个数字，不过，我必须打印它“不是一个一致列表”，因为第二个数字的前缀是第一个数字。

我最初的想法是一个嵌套的 for 循环...考虑到我随后必须测试 1 亿次比较，您可以看出这是一个多么糟糕的想法。我尝试了一个 bool 来打破这个嵌套循环，但后来意识到如果确实所有数字都有效那么我们仍然遇到问题。

tl;dr - 我需要一种快速的方法来比较 1-10000 个元素的字符串数组中的元素。如果一个字符串是另一个字符串的开头，那么它就是一个无效的数字列表。

我见过很多不同的东西，比如 SequenceEquals 和 LINQ 表达式，但我决定来这里寻求专业帮助。

更新代码

using System;

namespace ConsoleApp1
{
    class Program
    {
    static void Main(string[] args)
    {
        bool validTestNum = false;
        int testCases = 0;
        try
        {
            testCases = int.Parse(Console.ReadLine());
            validTestNum = true;
            if (testCases < 1 || testCases > 40)
            {
                validTestNum = false;
            }
        }
        catch { }

        for (int i = 0; i < testCases; i++)
        {
            bool validN = false;
            string nString = ""; //Needed string 
            int nNum = 0; //Needed num version for validation
            while (!validN)
            {
                nNum = int.Parse(Console.ReadLine());
                validN = true;
                if (nNum < 1 || nNum > 10000)
                    validN = false; //This is validating the amount of phone numbers received
            }

            nString = nNum.ToString();
            string[] numbers = new string[int.Parse(nString)];
            for (int j = 0; j < numbers.Length; j++)
            {
                numbers[j] = Console.ReadLine(); //This fills array with numbers
            }

            bool consistent = true; //Checking whether we detect any 'inconsistencies'
            Array.Sort(numbers); //Sorts string array

            for (int j = 1; j < numbers.Length; j++)
            {
                string possiblePrefix = numbers[j - 1];
                if (j < numbers.Length && numbers[j].StartsWith(possiblePrefix))
                {
                    consistent = false;
                    break;
                }
            }

            if (consistent)
            {
                Console.WriteLine("YES"); //Means the list is consistent
            }
            else if (!consistent)
            {
                Console.WriteLine("NO"); //Means it isn't
            }
        }
        Console.ReadLine();

    }
}

}

Answer 1

对数组进行排序。像“911”这样的较短数字将始终位于它所属的任何较长数字之前。排序列表示例：

所以，您所要做的就是检查给定的数字是否是下一个数字的开始。没了就停

Array.Sort(a);
for (int i = 1; i < a.Length; i++) { // Note: we start at index 1, not 0
    string possiblePrefix = a[i - 1];
    for (int k = i; k < a.Length && a[k].StartsWith(possiblePrefix); k++) {
        // a[k] is inconsistent with possiblePrefix , add it to a list or whatever.
        Console.WriteLine($"{possiblePrefix} - {a[k]}");
    }
}

请注意，对于大多数数字，内循环甚至不会开始循环。只有在发现不一致的极少数情况下，它才会循环。所以，这是一个接近 O(n) 的算法。排序是一个 O(n log(n)) 操作。

如果您只需要知道系列的第一个不一致，您也可以用一个简单的 if 替换内部循环。

Answer 2

这里有一个 LINQ 解决方案，如果您想走那条路：

static void Main(string[] args)
{
    var list = new List<string>
    {
        "1",
        "23",
        "456",
        "7890",
        "23457"
    };

    var prefixFound = false;
    foreach (var num in list)
    {
        if (list.Any(x => x.StartsWith(num) && x != num))
        {
            prefixFound = true;
            Console.WriteLine(num);
            break;
        }
    }
    if (!prefixFound)
        Console.WriteLine("Consistent list.");

    Console.ReadLine();
}

&& x != num条件是排除数字在技术上以自身开头的情况。

快速比较相同字符串数组的元素

Compare elements of same string array quickly

c#

arrays

sorting

comparison