0

给定一个大小为 x*y 的二维数组，其数字从 1 到 x*y 或 null ，条件如下 - m[x,y] == null || m[x,y] > m[x',y'] 其中 (x > x' && y = y') || (y > y')

例如：

2X2 array: 
4 0
0 0

2X2 array: 
3 0
0 4

编写一个算法，以最少的读取次数输出 1 到 x*y 之间缺失的数字列表。

4

2 回答 2

0

在这里，您有一个 C# 解决方案，但可以很容易地转换为 Java。主要思想是，在问题的定义下，一行中的最小值是您可以期望在前一行中找到的最大值。（同样的想法是，您在一行中找到的最大值是您在下一行中可以预期的最小值）。如果您找到了一行预期的最大值（或最小值），您不必继续访问矩阵，因为没有任何意义，然后您节省了很多步骤成为最佳解决方案。

static List<int> Missing(int[,] matrix, int x, int y)
{
    bool[] numbers = new bool[x * y + 1]; //All values found in the matrix
    int max = x * y; //Max possible value in a row
    int min = max; //Min possible value in a row
    int row = y - 1; //Starting from the last row in the matrix until the first one
    while ((row >= 0) && (min > 1)) //Stop accessing in case that the global possible minimum (value 1) is found in a row greater than first one
    {
        int col = -1;
        do
        {
            col++;
            if (matrix[row, col] > 0) //Assuming that value 0 means null
            {
                numbers[matrix[row, col]] = true; //Mark as found the value in the cell
                min = Math.Min(min, matrix[row, col]); //Update the minimun value of the row (first non zero value in the row)
            }
        }
        while ((col < x - 1) && (matrix[row, col] < max) && (min > 1)); //Inside the matrix range? Stop condition to do not access more elements in that row
        max = min - 1; //Update the possible maximum value for the following row (row - 1)
        row--;
    }
    var result = new List<int>();
    for (var index = 1; index <= x * y; index++)
        if (!numbers[index]) //Return only those values that were NOT found in the matrix
            result.Add(index);
    return result;
}

使用示例：

int[,] matrix =
{
    { 0,  2,  0, 11, 0 },
    { 0,  0,  0,  0, 0 },
    { 0, 12,  0, 15, 0 },
    { 0, 16,  0,  0, 0 },
    { 0,  0, 21, 25, 0 }
};
List<int> numbers = Missing(matrix, matrix.GetLength(0), matrix.GetLength(1));
for (int index = 0; index < numbers.Count - 1; index++)
    Console.Write(numbers[index].ToString() + " ");
Console.WriteLine(numbers.Count > 0 ? numbers[numbers.Count - 1].ToString() : string.Empty);

希望它能解决你的问题。

于 2012-08-11T03:48:47.590 回答
0

分配一个布尔数组，初始化为 false 大小 (x*y)

遍历矩阵中的所有单元并将 array(M(x,y)) 设置为 true

遍历数组并打印 array(i)=false 的所有索引

如果您正在寻找技巧，则缺失数字的总和（1to(x*y) 的总和 - 矩阵的总和）和缺失数字的数量可能足以确定它们是什么

于 2012-08-11T00:25:19.417 回答