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

问题描述

编辑：我认为网站上的 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 个唯一的电话号码。我必须检查数组中的一个号码是否是另一个号码的前缀，即'911'，是一个电话号码，'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();

    }
}

}

标签： c#arrayssortingcomparison

对数组进行排序。像“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如果您只需要知道系列的第一个不一致性，您也可以用简单的替换内部循环。

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

问题描述

解决方案

推荐阅读