我想在整数数组的连续子集中找到一个公共数字的最大频率

Question

数组A的部分数字子序列是一个整数子序列，其中每个连续的整数至少有1个公共数字我保留了一本包含 0 到 9 个字符的字典以及每个后续字符的计数。然后我遍历整数数组中的所有值并获取每个数字并检查我的字典中该数字的计数。public static void Main(string[] args){    Dictionary<char, int> dct = new Dictionary<char, int>    {        { '0', 0 },        { '1', 0 },        { '2', 0 },        { '3', 0 },        { '4', 0 },        { '5', 0 },        { '6', 0 },        { '7', 0 },        { '8', 0 },        { '9', 0 }    };    string[] arr = Console.ReadLine().Split(' ');    for (int i = 0; i < arr.Length; i++)    {        string str = string.Join("", arr[i].Distinct());        for (int j = 0; j < str.Length; j++)        {            int count = dct[str[j]];            if (count == i || (i > 0 && arr[i - 1].Contains(str[j])))            {                count++;                dct[str[j]] = count;            }            else dct[str[j]] = 1;        }    }    string s = dct.Aggregate((l, r) => l.Value > r.Value ? l : r).Key.ToString();    Console.WriteLine(s);}例如，12 23 231 答案是 2，因为它出现了 3 次该数组可以包含 10^18 个元素。有人可以帮我找到最佳解决方案吗？该算法不适合处理数组中的大数据。

Answer 1

所有发布的答案都是错误的，因为他们都忽略了问题中最重要的部分：

该数组可以包含 10^18 个元素。

正在从磁盘读取此阵列？假设每个元素是两个字节，那么阵列就有 200 万 TB 的驱动器。 我认为这不适合记忆。 您必须使用流媒体解决方案。

流媒体解决方案需要多长时间？如果您每秒可以处理 10 亿个数组项，这似乎是合理的，那么您的程序将需要 32 年才能执行。

你的要求不切实际，单靠一个人的资源是不可能解决的。您将需要大公司或国家的资源来解决这个问题，并且您将需要大量资金用于硬件采购和管理。

线性算法很简单；整个问题在于数据的大小。开始在电力便宜且税法友好的地方建立您的数据中心，因为您将要进口大量磁盘。

Answer 2

当然不是一个有效的解决方案，但这会奏效。

public class Program

{

    public static int arrLength = 0;

    public static string[] arr;

    public static Dictionary<char, int> dct = new Dictionary<char, int>();

    public static void Main(string[] args)

    {

        dct.Add('0', 0);

        dct.Add('1', 0);

        dct.Add('2', 0);

        dct.Add('3', 0);

        dct.Add('4', 0);

        dct.Add('5', 0);

        dct.Add('6', 0);

        dct.Add('7', 0);

        dct.Add('8', 0);

        dct.Add('9', 0);

        arr = Console.ReadLine().Split(' ');

        arrLength = arr.Length;

        foreach (string str in arr)

        {

            char[] ch = str.ToCharArray();

            ch = ch.Distinct<char>().ToArray();

            foreach (char c in ch)

            {

                Exists(c, Array.IndexOf(arr, str));

            }

        }

        int val = dct.Values.Max();

        foreach(KeyValuePair<char,int> v in dct.Where(x => x.Value == val))

        {

            Console.WriteLine("Common digit {0} with frequency {1} ",v.Key,v.Value+1);

        }

        Console.ReadLine();

    }

    public static bool Exists(char c, int pos)

    {

        int count = 0;

        if (pos == arrLength - 1)

            return false;

        for (int i = pos; i < arrLength - 1; i++)

        {

            if (arr[i + 1].ToCharArray().Contains(c))

            {

                count++;

                if (count > dct[c])

                    dct[c] = count;

            }

            else

                break;

        }

        return true;

    }

}