在不使用数组的情况下获取几个整数中出现次数最多的数字

Question

免责声明：这里是理论性问题，不是寻找正确答案，只是寻求一些灵感！

考虑一下：

一个函数被重复调用并且returns个基于种子的整数（相同的种子returns相同的整数）。你的任务是找出哪个整数最常被 returned。够简单吧？

但是：您不能使用数组或字段来存储上述函数的 return 值！

示例：

int mostFrequentNumber = 0;
int occurencesOfMostFrequentNumber = 0;
int iterations = 10000000;

for(int i = 0; i < iterations; i++)
{
    int result = getNumberFromSeed(i);
    int occurencesOfResult = magic();
    if(occurencesOfResult > occurencesOfMostFrequentNumber)
    {
        mostFrequentNumber = result;
        occurencesOfMostFrequentNumber = occurencesOfResult;
    }
}

If getNumberFromSeed() returns 2,1,5,18,5,6 和 5那么 mostFrequentNumber 应该是 5 而 occurencesOfMostFrequentNumber 应该是 3 因为 5 被 returned 3 次。

我知道使用二维列表存储结果和事件可以很容易地解决这个问题。但是想象一下，你不能使用任何类型的数组、列表、字典等。（可能是因为运行代码的系统内存有限，你不能一次存储足够的整数，或者因为你的史前编程语言没有集合的概念）。

如何找到 mostFrequentNumber 和 occurencesOfMostFrequentNumber？ magic() 是做什么的？（因为您不必拘泥于示例代码。欢迎提出任何想法！）

编辑： 我应该补充一点 getNumber() 编辑的整数 return 应该使用种子计算，所以相同的种子 returns 相同的整数（即 int result = getNumber(5); 这将始终为 result 分配相同的值）

Answer 1

做一个假设：假设整数的分布是正态分布。

从简单开始。有两个变量

。 N 目前读取的元素数

。 M1 所述元素的平均值。

将两个变量初始化为0。

每次读取新值时 x 将 N 更新为 N + 1 并将 M1 更新为 M1 + (x - M1)/N.

最后 M1 将等于所有值的平均值。如果分布为 Normal，则此值将具有较高的频率。

现在改进上面的。添加第三个变量：

M2 到目前为止 x 的所有值的所有 (x - M1)^2 的平均值。

将 M2 初始化为 0。现在获得一些关于 10 元素的小记忆。对于您阅读的每个新值 x，如上更新 N 和 M1，并将 M2 更新为：

M2 := M2 + (x - M1)^2 * (N - 1) / N

每一步 M2 是分布的方差，sqrt(M2) 是它的标准差。

在你继续的过程中，只记住到目前为止读取到 M1 的距离小于 sqrt(M2) 的值的频率。这需要使用一些额外的数组，但是，与您将运行进行的大量迭代相比，该数组将非常短。此修改将使您能够更好地猜测最常见的值，而不是像上面那样简单地回答均值（或平均值）。

更新

鉴于这是关于灵感的见解，因此有足够的空间来考虑和调整我提出的方法以适应任何特定情况。这里有一些想法

当我说假设分布是正态分布时你应该这样想：鉴于问题没有解决方案，让我们看看是否有一些我可以使用定性信息来决定数据的分布类型。鉴于该算法旨在找到最频繁出现的数字，假设分布不均匀应该没问题。让我们尝试使用 Normal、LogNormal 等，看看可以找到什么（更多内容见下文。）
如果游戏完全不允许使用任何数组，那好吧，只记录，比如10个数字。这将允许您计算 10 个最佳候选的出现次数，这将使您的答案更有信心。在这样做时，根据你的假设的分布，在理论上最可能的值附近选择你的候选人。
您不能使用数组，但也许您可以读取数字序列两到三次，而不仅仅是一次。在那种情况下，您可以阅读一次以检查您对其分布的假设是好是坏。例如，如果您不仅计算方差，还计算偏度和峰度，您将有更多元素来检查您的假设。例如，如果第一个读数表明存在一些偏差，则可以改用 LogNormal 分布等
最后，除了提供大致答案外，您还可以使用阅读过程中收集的信息来估计您答案的置信区间。

Answer 2

好吧，我自己找到了一个不错的解决方案：

int mostFrequentNumber = 0;
int occurencesOfMostFrequentNumber = 0;
int iterations = 10000000;
int maxNumber = -2147483647;
int minNumber = 2147483647;

//Step 1: Find the largest and smallest number that _can_ occur
for(int i = 0; i < iterations; i++)
{
    int result = getNumberFromSeed(i);
    if(result > maxNumber)
    {
        maxNumber = result;
    }
    if(result < minNumber)
    {
        minNumber = result;
    }
}

//Step 2: for each possible number between minNumber and maxNumber, count occurences
for(int thisNumber = minNumber; thisNumber <= maxNumber; thisNumber++)
{
    int occurenceOfThisNumber = 0;
    for(int i = 0; i < iterations; i++)
    {
        int result = getNumberFromSeed(i);
        if(result == thisNumber)
        {
            occurenceOfThisNumber++;
        }
    }
    if(occurenceOfThisNumber > occurencesOfMostFrequentNumber)
    {
        occurencesOfMostFrequentNumber = occurenceOfThisNumber;
        mostFrequentNumber = thisNumber;
    }   
}

我必须承认，这可能需要很长时间，具体取决于可能的最小值和最大值。但它可以在不使用数组的情况下工作。

在不使用数组的情况下获取几个整数中出现次数最多的数字

Get the most occuring number amongst several integers without using arrays

frequency

pseudocode