0

1 から x*y までの数値を持つサイズ x*y の 2D 配列、または次の条件で 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

サイズ (x*y) の false に初期化されたブール値の配列を割り当てます

マトリックス内のすべてのセルを調べて、array(M(x,y)) を true に設定します

配列を調べて、array(i)=false のすべてのインデックスを出力します

トリックを探している場合は、不足している数字の合計 (1to(x*y) - マトリックスの合計) と不足している数字の量で、それらが何であるかを判断するのに十分な場合があります。

于 2012-08-11T00:25:19.417 に答える