logo标签列表

我想找到整数数组连续子集中常见数字的最高频率。

c#arraysalgorithmdata-structuresdynamic
3
数组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个元素。

有人能帮我找到最优解吗？这个算法无法处理数组中的大数据。

计算整数中重复出现的次数没有意义，因为我想要从整数数组中获得最大计数。 - amit tiwari
啊，我明白了。 - TheGeneral
@kaarthickraman 112，432，812，192，111，113，221 这里的答案是1， 因为它在3、4、5、6、7索引（连续）处出现。 - amit tiwari
在最近的5个中，有1个。因此答案是1。 - amit tiwari
1
12 23 231 4444 444 应该也算作2吗？ - TheGeneral
显示剩余19条评论
6个回答
9
所有发布的答案都是错误的，因为它们都忽略了问题最重要的部分：

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

这个数组是从磁盘中读取的吗？假设每个元素是两个字节，那么仅对于数组就需要200万个太字节驱动器。我认为这不可能放入内存中。你必须使用流式解决方案。
流式解决方案需要多长时间？如果你能够处理一秒钟十亿个数组项，这似乎是合理的，那么你的程序将需要32年才能执行。
你的要求并不现实，因此无法仅凭单个人的资源解决这个问题。你需要一个大公司或国家的资源来攻击这个问题，并且你需要大量的硬件采购和管理资金。
线性算法很简单；数据大小才是整个问题所在。开始在某个具有便宜的电力和友好税法的地方建立你的数据中心，因为你将会导入大量的磁盘。
是的，10^18是一个很大的数字。我假设他想要一个能够处理高达那个数字的算法。而且你是对的，需要最小内存的线性算法是微不足道的。 - Jim Mischel
@JimMischel：没错，算法根本不是问题所在。问题陈述得不好。如果意图是说“一个解决方案，在内存负担上保持恒定，且时间复杂度随输入规模线性增长”，那么这就是应该提出的问题。我不知道这个10的18次方数字是从哪里来的。 - Eric Lippert
@EricLippert 10^18大约是2^60。嗯，至少比“我想枚举所有的GUID，全部都要”好一点。 - Joker_vD
0

这肯定不是一个高效的解决方案，但它可以工作。

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;
    }
}
0
正如其他人指出的那样，如果你有10^18个数字，那么这将是比你可以装入内存的数据要多得多。因此，你需要一个流式解决方案。你也不想花费很多时间在内存分配或将字符串转换为字符数组、调用函数来去重数字等方面。理想情况下，你需要一个只查看每个字符一次的解决方案。
下面程序的内存需求非常小：只有两个小的长整型数组。
我开发的算法维护了两个每个数字计数的数组。一个是数字连续出现的最大次数，另一个是最近连续出现的计数。
代码本身按字符读取文件，累积数字，直到遇到一个不是数字的字符，然后更新每个数字遇到的当前计数数组。如果当前计数超过了最大计数，则更新该数字的最大计数。如果一个数字在一个数字中没有出现，则它的当前计数被重置为0。
数字的单个数字的出现通过在digits变量中设置位来维护。这样，像1221这样的数字就不会计算两次。
using (var input = File.OpenText("filename"))
{
    var maxCounts = new long[]{0,0,0,0,0,0,0,0,0,0};
    var latestCounts = new long[]{0,0,0,0,0,0,0,0,0,0};
    char prevChar = ' ';

    word digits = 0;
    while (!input.EndOfStream)
    {
        var c = input.Read();

        // If the character is a digit, set the corresponding bit
        if (char.IsDigit(c))
        {
            digits |= (1 << (c-'0'));
            prevChar = c;
            continue;
        }

        // test here to prevent resetting counts when there are multiple non-digit
        // characters between numbers.
        if (!char.IsDigit(prevChar))
        {
            continue;
        }
        prevChar = c;

        // digits has a bit set for every digit
        // that occurred in the number.
        // Update the counts arrays.

        // For each of the first 10 bits, update the corresponding count.
        for (int i = 0; i < 10; ++i)
        {
            if ((digits & 1) == 1)
            {
                ++latestCounts[i];
                if (latestCounts[i] > maxCounts[i])
                {
                    maxCounts[i] = latestCounts[i];
                }
            }
            else
            {
                latestCounts[i] = 0;
            }
            // Shift the next bit into place.
            digits >> 1;
        }
        digits = 0;
    }
}

这段代码最小化了所需的处理，但程序的运行时间将受到您读取文件的速度支配。有一些优化可以提高输入速度，但最终您仍然受限于系统的数据传输速度。

0

你不需要逐个遍历数组元素，可以将整个字符串数组合并为一个字符串，然后遍历其中的字符。

12 23 231 -> "1223231"，循环遍历并计数。

这应该足够快，时间复杂度为O(n)，只需要在字典中使用10个条目。你需要多快？

假设数组是21 32 132，那么合并不会有帮助，对吧？ - amit tiwari
0

我没有使用数组，不确定是否必须使用数组，如果不需要，请检查此解决方案。

static void Main(string[] args)
    {
        List<char> numbers = new List<char>();
        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 option;

        do
        {
            Console.Write("Enter number: ");
            string number = Console.ReadLine();
            numbers.AddRange(number);

            Console.Write("Enter 'X' if u want to finish work: ");
            option = Console.ReadLine();

        } while (option.ToLower() != "x");

        foreach(char c in numbers)
        {
            if(dct.ContainsKey(c))
            {
                dct[c]++;
            }
        }

        foreach(var keyValue in dct)
        {
            Console.WriteLine($"Char {keyValue.Key} was used {keyValue.Value} times");
        }

        Console.ReadKey(true);
    }
如果数组是112 221 232 251 113 114，它将无法通过测试用例。它会输出1，因为它出现了5次，但正确答案是2，因为它连续出现了4次。 - amit tiwari
我不是很明白，你能解释一下你想得到什么吗？我以为你想要数字使用的数量。 - Serlok
12 23 231 4444 444 的最长公共子序列是2，因为数字2在0、1、2索引位置都出现了。 - amit tiwari
0

我会给你三个版本。

基本上，我只是将随机整数列表作为字符串加载，规模是多少，然后在Core和Framework上运行它。每个测试运行了10次并取平均值。

Mine1

使用Distinct。

public unsafe class Mine : Benchmark<List<string>, char>
{
   protected override char InternalRun()
   {
      var result = new int[10];
      var asd = Input.Select(x => new string(x.Distinct().ToArray())).ToList();
      var raw = string.Join("", asd);

      fixed (char* pInput = raw)
      {
         var len = pInput + raw.Length;
         for (var p = pInput; p < len; p++)
         {
            result[*p - 48]++;
         }
      }

      return (char)(result.ToList().IndexOf(result.Max()) + '0');
   }
}

Mine2

基本上，这个程序使用第二个数组来处理事情。

public unsafe class Mine2 : Benchmark<List<string>, char>
{
   protected override char InternalRun()
   {
      var result = new int[10];
      var current = new int[10];
      var raw = string.Join(" ", Input);

      fixed (char* pInput = raw)
      {
         var len = pInput + raw.Length;
         for (var p = pInput; p < len; p++)
            if (*p != ' ')
               current[*p - 48] = 1;
            else
               for (var i = 0; i < 10; i++)
               {
                  result[i] += current[i];
                  current[i] = 0;
               }
 
      }

      return (char)(result.ToList().IndexOf(result.Max()) + '0');
   }
}

Mine3

无需连接或字符串分配。

public unsafe class Mine3 : Benchmark<List<string>, char>
{
   protected override char InternalRun()
   {
      var result = new int[10];

      foreach (var item in Input)
         fixed (char* pInput = item)
         {
            var current = new int[10];
            var len = pInput + item.Length;

            for (var p = pInput; p < len; p++)
               current[*p - 48] = 1;

            for (var i = 0; i < 10; i++)
            {
               result[i] += current[i];
               current[i] = 0;
            }
         }
         

      return (char)(result.ToList().IndexOf(result.Max()) + '0');
   }
}

#结果 .Net Framework 4.7.1

Mode            : Release
Test Framework  : .Net Framework 4.7.1
Benchmarks runs : 10 times (averaged)

Scale : 10,000
Name     |   Average |   Fastest | StDv |     Cycles | Pass |        Gain
--------------------------------------------------------------------------
Mine3    |  0.533 ms |  0.431 ms | 0.10 |  1,751,372 | Base |      0.00 %
Mine2    |  0.994 ms |  0.773 ms | 0.38 |  3,100,896 | Yes  |    -86.63 %
Mine     |  8.122 ms |  7.012 ms | 1.29 | 27,480,083 | Yes  | -1,424.78 %
Original | 20.729 ms | 16.044 ms | 4.56 | 65,316,558 | No   | -3,791.47 %


Scale : 100,000
Name     |    Average |    Fastest |  StDv |      Cycles | Pass |        Gain
------------------------------------------------------------------------------
Mine3    |   4.766 ms |   4.475 ms |  0.34 |  16,140,716 | Base |      0.00 %
Mine2    |   8.424 ms |   7.890 ms |  0.33 |  28,577,416 | Yes  |    -76.76 %
Mine     |  96.650 ms |  93.066 ms |  3.35 | 327,615,266 | Yes  | -1,927.94 %
Original | 163.342 ms | 154.070 ms | 12.61 | 550,038,934 | No   | -3,327.32 %


Scale : 1,000,000
Name     |      Average |      Fastest |  StDv |        Cycles | Pass |        Gain
------------------------------------------------------------------------------------
Mine3    |    49.827 ms |    48.600 ms |  1.19 |   169,162,589 | Base |      0.00 %
Mine2    |   106.334 ms |    97.641 ms |  6.53 |   359,773,719 | Yes  |   -113.41 %
Mine     | 1,051.600 ms | 1,000.731 ms | 35.75 | 3,511,515,189 | Yes  | -2,010.51 %
Original | 1,640.385 ms | 1,588.431 ms | 65.50 | 5,538,915,638 | No   | -3,192.18 %

#结果 .Net Core 2.0

Mode            : Release
Test Framework  : Core 2.0
Benchmarks runs : 10 times (averaged)

Scale : 10,000
Name     |   Average |   Fastest | StDv |     Cycles | Pass |        Gain
--------------------------------------------------------------------------
Mine3    |  0.476 ms |  0.353 ms | 0.12 |  1,545,995 | Base |      0.00 %
Mine2    |  0.554 ms |  0.551 ms | 0.00 |  1,883,570 | Yes  |    -16.23 %
Mine     |  7.585 ms |  5.875 ms | 1.27 | 25,580,339 | Yes  | -1,492.28 %
Original | 21.380 ms | 16.263 ms | 6.46 | 65,741,909 | No   | -4,388.14 %


Scale : 100,000
Name     |    Average |    Fastest |  StDv |      Cycles | Pass |        Gain
------------------------------------------------------------------------------
Mine3    |   3.946 ms |   3.685 ms |  0.25 |  13,409,181 | Base |      0.00 %
Mine2    |   6.203 ms |   5.796 ms |  0.33 |  21,042,340 | Yes  |    -57.21 %
Mine     |  72.975 ms |  68.599 ms |  4.13 | 246,471,960 | Yes  | -1,749.41 %
Original | 161.400 ms | 145.664 ms | 19.37 | 544,703,761 | Yes  | -3,990.40 %


Scale : 1,000,000
Name     |      Average |      Fastest |  StDv |        Cycles | Pass |        Gain
------------------------------------------------------------------------------------
Mine3    |    41.036 ms |    38.928 ms |  2.47 |   139,045,736 | Base |      0.00 %
Mine2    |    71.283 ms |    68.777 ms |  2.49 |   241,525,269 | Yes  |    -73.71 %
Mine     |   749.250 ms |   720.809 ms | 27.79 | 2,479,171,863 | Yes  | -1,725.84 %
Original | 1,517.240 ms | 1,477.321 ms | 48.94 | 5,142,422,700 | No   | -3,597.35 %

#概述

字符串分配、连接和去重对性能有很大影响。如果您需要更高的性能，可以将列表分解成工作负载，并并行处理。

1
你的代码是否能够产生正确的结果？给定输入 123 196 32 475 38，答案应该是 1，因为它是连续数字中出现最多的数字。看起来你的代码会返回 3，因为它是出现最多的数字。 - Jim Mischel
@JimMischel 你说得对，我的代码会返回最常见的数字，而不是连续的数字。 - TheGeneral
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接