用于最小化2D阵列中的读取次数的算法

Given a 2D array of size x*y with numbers from 1 to x*y or null with the following condition - m[x,y] == null || m[x,y] > m[x',y'] where (x > x' && y = y') || (y > y')

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

For example:

2X2 array: 
4 0
0 0

2X2 array: 
3 0
0 4

Write an algorithm to output the list of numbers that are missing between 1 and x*y with minimum number of reads.

编写一个算法,以最小的读数输出1和x * y之间缺失的数字列表。

2 个解决方案

#1

allocate an array of booleans inited to false of size (x*y)

分配一个布尔数组,其大小为假(x * y)

go over all of the cells in the matrix and set array(M(x,y)) to true

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

go over the array and print all indexes where array(i)=false

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

if you are looking for a trick the sum of the missing numbers (sum of 1to(x*y) -sum of matrix) and amount of the missing numbers might be enough to determine what they are

如果你正在寻找一个技巧,缺失数字的总和(矩阵的1到(x * y) - 总和的总和)和缺失数量的数量可能足以确定它们是什么

#2

Here you have a solution in C# but can be translated to Java very easy. The main idea is that under the definition of the problem the minimum value in a row is the maximum value that you can expect to find in a previous row. (The same idea is that the maximum value that you found in a row is the minimum value that you can expect in a following row). If you found the maximum value (or minimum) expected for a row you don't have to continue accessing to the matrix because don't have any sense and then you save a lot of steps becoming optimum solution.

在这里你有一个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;
}

Example of usage:

用法示例:

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);

Hopefully it'll solve your problem.

希望它能解决你的问题。

#1