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

Question

数组A的部分数字子序列是整数的子序列,其中每个连续的整数至少有一个共同的数字

我保留一个包含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的驱动器只用于阵列. 我不认为这会适合记忆. 你必须使用流媒体解决方案.

流媒体解决方案需要多长时间？如果您可以在一秒钟内处理十亿个数组项目,这似乎是合理的,那么您的程序将需要32年才能执行.

您的要求不切合实际,因此单个人的资源无法解决问题.您需要大型公司或国家的资源来解决此问题,并且您需要大量资金来进行硬件采购和管理.

线性算法是微不足道的; 这是整个问题的数据大小.开始使用廉价的电源和友好的税法在某个地方建立您的数据中心,因为您将要导入大量磁盘.