如何在二维整数数组中找到最常见的整数?

它至少是O(n*m),不管你用什么方法切片它——你必须至少看一次每个细胞。节约的地方在于,在寻找最常见的值之前,先累积每个值的计数;如果整数在一个相对较小的范围内变化(比如说,它们是uint16),那么您可以简单地使用平面数组而不是映射。

我想你也可以继续计数 x , “最常见”和“最接近”的当前排名前和第二的候选人,并且在剩下(n*m)-(x-y)个单元格时尽早退出,因为在这一点上,亚军不可能超过排名第一的候选人。

像这样的整数运算相当快;即使是一张百万像素的图像,暴力算法也只需要几毫秒。

我注意到你已经编辑了你的原始问题,说像素值从0到255——在这种情况下,一定要使用一个简单的平面数组;它足够小,可以很容易地放入l1dcache,而平面数组中的查找是trez-quick。

[编辑]: 一旦你建立了直方图数组,处理“没有最常见的数字”的情况非常简单:你所要做的就是遍历它,找到“最多”和“第二最多”的常见数字;如果它们同样频繁,那么根据定义,没有一个是最常见的。

const int numLevels = 360; // you said each cell contains a number [0..360)
int levelFrequencyCounts[numLevels]; // assume this has been populated such that levelFrequencyCounts[i] = number of cells containing "i"
int mostCommon = 0, runnerUp = 0;
for (int i = 1 ; i < numLevels ; ++i)
{
  if ( levelFrequencyCounts[i] > levelFrequencyCounts[mostCommon] )
  {
    runnnerUp = mostCommon;
    mostCommon = i;
  }
}

if ( levelFrequencyCounts[mostCommon] != levelFrequencyCounts[runnerUp] )
{
   return mostCommon;
}
else
{
   return CenterOfInputData; // (something like InputData[n/2][m/2])
}

在C#中,我将如何做类似的事情?

大概是这样的:

Dictionary<int, int> d = new Dictionary<int, int>();
foreach (int value in matrix)
{
 if (!d.ContainsKey(value))
  d.Add(value, 1);
 else
  d[value] = d[value] + 1;
}
KeyValuePair<int, int> biggest = null;
foreach (KeyValuePair<int, int> found in d)
{
  if ((biggest == null) || (biggest.Value < found.Value))
    biggest = found;
}

一个选项是LINQ—效率有点低,但对于非大型阵列来说还可以:

    var max = (from cell in data.Cast<int>()
               group cell by cell into grp
               select new { Key = grp.Key, Count = grp.Count() } into agg
               orderby agg.Count descending
               select agg).First();
    Console.WriteLine(max.Key + ": " + max.Count);

或者使用锯齿状阵列:

    var max = (from row in data
              from cell in row
              group cell by cell into grp
              select new {Key = grp.Key, Count = grp.Count()} into agg
              orderby agg.Count descending
              select agg).First();
    Console.WriteLine(max.Key + ": " + max.Count);

    Dictionary<int, int> counts = new Dictionary<int, int>();
    foreach (int value in data)
    {
        int count;
        counts.TryGetValue(value, out count);
        counts[value] = count + 1;
    }
    int maxCount = -1, maxValue = 0;
    foreach (KeyValuePair<int, int> pair in counts)
    {
        if (pair.Value > maxCount)
        {
            maxCount = pair.Value;
            maxValue = pair.Key;
        }
    }
    Console.WriteLine(maxCount + ": " + maxValue);

300+ 300+ 300+ 300 300 300 300
  0+ 150+ 300+ 300 300 300 300
  0+   0+ 150+ 300 300 300 300
  0    0    0    0 300 300 300
  0    0    0    0 150 300 300
  0    0    0    0   0 150 300
  0    0    0    0   0   0 300

标记的(+)数字是您的窗口。w、 h是您的窗口尺寸。申请 bucket sorting (正如其他人所建议的,因为您的值范围非常有限)。不要把你的评价降低一半 Crashworks 建议。现在还不要放弃你的结果。这是第一步。

300- 300- 300- 300 300 300 300
  0. 150. 300. 300 300 300 300
  0.   0. 150. 300 300 300 300
  0+   0+   0+   0 300 300 300
  0    0    0    0 150 300 300
  0    0    0    0   0 150 300
  0    0    0    0   0   0 300

换句话说,您需要像这样移动窗口:

|  ^->|  ^
|  |  |  |
|  |  |  |
V->|  V->|

我假设您正在尝试实现一个非线性卷积滤波器。

欢迎指正。

// stores hit counts (0-360)
short[] hitCounts = new short[361];

// iterate through 2d array and increment hit counts
for (int i = 0; i < toEvaluate.Length; i++)
{
    for (int j = 0; j < toEvaluate[i].Length; j++)
        hitCounts[toEvaluate[i][j]]++;
}

int greatestHitCount = 0; // the hit count of the current greatest value
int greatest = -1; // the current greatest valeu

// iterate through values (0-360) and evalute hit counts
for (int i = 0; i < hitCounts.Length; i++)
{
    // the hit count of hitCounts[i] is higher than the current greatest hit count value
    if (hitCounts[i] > greatestHitCount)
    {
        greatestHitCount = vals[i]; // store the new hit count
        greatest = i; // store the greatest value
    }
    // there is already a value with the same hit count (which is the greatest)
    else if (hitCounts[i] == greatestHitCount)
        greatest = -1; // there are more than one value, we can't use this if it ends up being the greatest
}

if (greatest >= 0) // no greatest value found
    return greatest;

// figure out the middle x and y value
int x = (toEvaluate.Length - 1) / 2 + 1;
int y = (toEvaluate[x].Length - 1) / 2 + 1;

// return the value at the center of the 2d array as the value
return toEvaluate[x][y];

当速度成为一个关于可读性的问题时,你最终必然会得到丑陋的代码。上述内容肯定会从重构中受益(因此注释过多),但它应该运行得很快。如果速度不够快,您可以通过将其移动到非托管代码来获得更多优化。

请看一下Paint.NET中的LocalHistorgRameEffect代码,特别是LocalHistorgRameEffect.RenderRect。

调整此选项以支持色调而不是RGB强度将非常简单。

性能相当好,并且出于您的目的,它在O(r^2+w)模式下运行 r+n w) ,其中r是半径,w是图像的宽度,n是直方图中的层数。

-杰克逊

迈克尔击败了我,但我也会这样做,比如:

        int MaxValueIn2dArray(int[,] matrix)
    {
        var d = new int[360];
        int MaxValue = 0;
        for (int x = 0; x <= matrix.GetUpperBound(0); x++)
        {
            for (int y = 0; y <= matrix.GetUpperBound(1); y++)
            {
                d[matrix[x, y]]++;
            }
        }
        foreach (int value in d)
        {
            if (value > MaxValue) MaxValue = value;
        }
        return MaxValue;
    }

它需要针对您的特定需求进行优化。

1.)确保当当前最常见值的计数大于;(M x N/2)。如果某件事发生了>50%的网络覆盖率是最常见的价值,无需继续。如果你的日常工作只需要在大部分时间是正确的,那么你可以降低百分比,并将其视为一种启发。您甚至可以运行一些分析,分析出覆盖率是否为>37.6%,然后99.9%的时间它将是最常见的值,然后使用该百分比。

2.)如果有任何方法可以确定最常见的值可能位于哪一侧、角落或一般位置(外边缘、中间等),则可以按照该顺序扫描,再加上上面的优化1,可以减少大量扫描。例如,在您的示例中,右上角重于公共值。如果这可以通过某种启发式方法确定,那么您可以以某种方式从右上角扫描到左下角。如果所需的扫描模式复杂,请预先生成。