Установите каждую ячейку в матрице в 0, если эта строка или столбец содержит 0

Question

Учитывая матрицу NxN с 0 и 1. Установите каждую строку, содержащую 0, для всех 0 с и установите каждый столбец, содержащий 0, для всех 0 с.

Например

1 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1

Результаты в

0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0

Инженер Microsoft сказал мне, что существует решение, не требующее дополнительной памяти, только две логические переменные и один проход, поэтому я ищу этот ответ.

Кстати, представьте, что это битовая матрица, поэтому в матрице допускается только 1 и 0.

Answer 1

1 проход, 2 логических значения. Я просто должен предположить, что целочисленные индексы в итерациях не учитываются.

Это не полное решение, но я не могу пройти этот пункт.

Если бы я мог только определить, является ли 0 исходным 0 или 1, преобразованным в 0, я бы не использовал -1, и это сработало бы.

Мой вывод такой:

-1  0 -1 -1  0
 0 -1 -1 -1  0
-1 -1  1  1 -1
-1  0 -1 -1 -1
-1 -1  1  1 -1

Оригинальность моего подхода заключается в использовании первой половины проверки строки или столбца, чтобы определить, содержит ли она 0, а в последней половине - для установки значений - это делается путем просмотра x и width-x, а затем y и height-y в каждой итерации. Исходя из результатов первой половины итерации, если в строке или столбце был найден 0, я использую последнюю половину итерации, чтобы изменить 1 на -1.

Я только что понял, что это можно сделать только с одним логическим значением, оставляя 1 для ...?

Я публикую это в надежде, что кто-то скажет: «А, просто сделай это ...» (И я потратил слишком много времени на это, чтобы не писать.)

Вот код в VB:

Dim D(,) As Integer = {{1, 0, 1, 1, 1}, {0, 1, 1, 0, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {0, 0, 1, 1, 1}}

Dim B1, B2 As Boolean

For y As Integer = 0 To UBound(D)

    B1 = True : B2 = True

    For x As Integer = 0 To UBound(D)

        // Scan row for 0's at x and width - x positions. Halfway through I'll konw if there's a 0 in this row.
        //If a 0 is found set my first boolean to false.
        If x <= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then
            If D(x, y) = 0 Or D(UBound(D) - x, y) = 0 Then B1 = False
        End If

        //If the boolean is false then a 0 in this row was found. Spend the last half of this loop
        //updating the values. This is where I'm stuck. If I change a 1 to a 0 it will cause the column
        //scan to fail. So for now I change to a -1. If there was a way to change to 0 yet later tell if
        //the value had changed this would work.
        If Not B1 Then
            If x >= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then
                If D(x, y) = 1 Then D(x, y) = -1
                If D(UBound(D) - x, y) = 1 Then D(UBound(D) - x, y) = -1
            End If
        End If

        //These 2 block do the same as the first 2 blocks but I switch x and y to do the column.
        If x <= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then
            If D(y, x) = 0 Or D(y, UBound(D) - x) = 0 Then B2 = False
        End If

        If Not B2 Then
            If x >= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then
                If D(y, x) = 1 Then D(y, x) = -1
                If D(y, UBound(D) - x) = 1 Then D(y, UBound(D) - x) = -1
            End If
        End If

    Next
Next

Answer 2

Вы можете сделать что-то вроде этого, чтобы использовать один проход, кроме матрицы ввода и вывода:

output(x,y) = col(xy) & row(xy) == 2^n

где col(xy) - биты в столбце, содержащем точку xy; row(xy) - биты в строке, содержащей точку xy. n - это размер матрицы.

Тогда просто зациклите ввод. Возможно расширяемый, чтобы быть более экономичным?

Answer 3

создать матрицу результатов и установить все значения в 1. пройти матрицу данных, как только встретится 0, установить столбец строки матрицы результатов на 0

В конце первого прохода матрица результатов будет иметь правильный ответ.

Выглядит довольно просто. Есть ли уловка, которую я пропускаю? Вам не разрешено использовать набор результатов?

EDIT:

Похоже на функцию F #, но это немного обманывает, поскольку, даже если вы делаете один проход, функция может быть рекурсивной.

Похоже, что интервьюер пытается выяснить, знаете ли вы функциональное программирование.

Answer 4

Один проход - я прошел вход только один раз, но использовал новый массив и только две дополнительные логические переменные.

public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();

        boolean rowDel = false, colDel = false;
        int arr[][] = new int[n][n];
        int res[][] = new int[n][n];
        int i, j;
        for (i = 0; i < n; i++) {

            for (j = 0; j < n; j++) {
                arr[i][j] = sc.nextInt();
                res[i][j] = arr[i][j];  
            }
        }

        for (i = 0; i < n; i++) {

            for (j = 0; j < n; j++) {
                if (arr[i][j] == 0)
                    colDel = rowDel = true; //See if we have to delete the
                                            //current row and column
                if (rowDel == true){
                    res[i] = new int[n];
                    rowDel = false;
                }
                if(colDel == true){
                    for (int k = 0; k < n; k++) {
                        res[k][j] = 0;
                    }
                    colDel = false;
                }

            }

        }

        for (i = 0; i < n; i++) {

            for (j = 0; j < n; j++) {
                System.out.print(res[i][j]);
            }
            System.out.println();
        }
        sc.close();

    }

Answer 5

Приведенный ниже код создает матрицу размером m, n. Сначала определитесь с размерами матрицы. Я хотел заполнить матрицу [m] [n] случайным образом числами от 0,10. Затем создайте другую матрицу с такими же размерами и заполните ее -1 с (окончательная матрица). Затем выполните итерацию по исходной матрице, чтобы увидеть, достигнете ли вы 0. Когда вы нажмете на местоположение (x, y), перейдите к финальной матрице и заполните строку x 0 и столбец y 0. В конце прочитайте окончательную матрицу, если значение равно -1 (исходное значение), скопируйте значение в том же месте исходной матрицы в конечную.

public static void main(String[] args) {
    int m = 5;
    int n = 4;
    int[][] matrixInitial = initMatrix(m, n); // 5x4 matrix init randomly
    int[][] matrixFinal = matrixNull(matrixInitial, m, n); 
    for (int i = 0; i < m; i++) {
        System.out.println(Arrays.toString(matrixFinal[i]));
    }
}

public static int[][] matrixNull(int[][] matrixInitial, int m, int n) {
    int[][] matrixFinal = initFinal(m, n); // create a matrix with mxn and init it with all -1
    for (int i = 0; i < m; i++) { // iterate in initial matrix
        for (int j = 0; j < n; j++) {
            if(matrixInitial[i][j] == 0){ // if a value is 0 make rows and columns 0
                makeZeroX(matrixFinal, i, j, m, n); 
            }
        }
    }

    for (int i = 0; i < m; i++) { // if value is -1 (original) copy from initial
        for (int j = 0; j < n; j++) {
            if(matrixFinal[i][j] == -1) {
                matrixFinal[i][j] = matrixInitial[i][j];
            }
        }
    }
    return matrixFinal;
}

private static void makeZeroX(int[][] matrixFinal, int x, int y, int m, int n) {
        for (int j = 0; j < n; j++) { // make all row 0
            matrixFinal[x][j] = 0;
        }
        for(int i = 0; i < m; i++) { // make all column 0
            matrixFinal[i][y] = 0; 
        }
}

private static int[][] initMatrix(int m, int n) {

    int[][] matrix = new int[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            Random rn = new Random();
            int random = rn.nextInt(10);
            matrix[i][j] = random;
        }
    }

    for (int i = 0; i < m; i++) {
        System.out.println(Arrays.toString(matrix[i]));
    }
    System.out.println("******");
    return matrix;
}

private static int[][] initFinal(int m, int n) {

    int[][] matrix = new int[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            matrix[i][j] = -1;
        }
    }
    return matrix;
}

// another approach
/**
 * @param matrixInitial
 * @param m
 * @param n
 * @return
 */
private static int[][] matrixNullNew(int[][] matrixInitial, int m, int n) {
    List<Integer> zeroRowList = new ArrayList<>(); // Store rows with 0
    List<Integer> zeroColumnList = new ArrayList<>(); // Store columns with 0
    for (int i = 0; i < m; i++) { // read through the matrix when you hit 0 add the column to zeroColumnList and add
                                  // the row to zeroRowList
        for (int j = 0; j < n; j++) {
            if (matrixInitial[i][j] == 0) {
                if (!zeroRowList.contains(i)) {
                    zeroRowList.add(i);
                }
                if (!zeroColumnList.contains(j)) {
                    zeroColumnList.add(j);
                }
            }
        }
    }

    for (int a = 0; a < m; a++) {
        if (zeroRowList.contains(a)) { // if the row has 0
            for (int b = 0; b < n; b++) {
                matrixInitial[a][b] = 0; // replace all row with zero
            }
        }
    }

    for (int b = 0; b < n; b++) {
        if (zeroColumnList.contains(b)) { // if the column has 0
            for (int a = 0; a < m; a++) {
                matrixInitial[a][b] = 0; // replace all column with zero
            }
        }
    }
    return matrixInitial;
}

Answer 6

Вы можете сделать это за один проход - если вы не учитываете доступ к матрице в порядке произвольного доступа, что исключает преимущества выполнения этого за один проход в первую очередь (кэш-когерентность / память-пропускная способность) ).

[редактировать: простое, но неправильное решение удалено]

Вы должны получить лучшую производительность, чем любой однопроходный метод, выполнив это за два прохода: один для накопления информации о строке / столбце и один для ее применения. Доступ к массиву (в порядке следования строк) связан; для массивов, превышающих размер кеша (но строки которых могут уместиться в кеше), данные должны считываться из памяти дважды и сохраняться один раз:

void fixmatrix2(int M[][], int rows, int cols) {
    bool clearZeroRow= false;
    bool clearZeroCol= false;
    for(int j=0; j < cols; ++j) {
        if( ! M[0][j] ) {
            clearZeroRow= true;
        }
    }
    for(int i=1; i < rows; ++i) { // scan/accumulate pass
        if( ! M[i][0] ) {
            clearZeroCol= true;
        }
        for(int j=1; j < cols; ++j) {
            if( ! M[i][j] ) {
                M[0][j]= 0;
                M[i][0]= 0;
            }
        }
    }
    for(int i=1; i < rows; ++i) { // update pass
        if( M[i][0] ) {
            for(int j=0; j < cols; ++j) {
                if( ! M[j][0] ) {
                    M[i][j]= 0;
                }
            }
        } else {
            for(int j=0; j < cols; ++j) {
                M[i][j]= 0;
            }
        }
        if(clearZeroCol) {
            M[i][0]= 0;
        }
    }
    if(clearZeroRow) {
        for(int j=0; j < cols; ++j) {
            M[0][j]= 0;
        }
    }
}

Answer 7

Ну, я придумал однопроходное (нерекурсивное) решение на месте, используя 4 bools и 2 счетчика цикла. Мне не удалось уменьшить его до 2 bools и 2 int, но я не удивлюсь, если бы это было возможно. Это делает приблизительно 3 чтения и 3 записи каждой ячейки, и это должно быть O (N ^ 2) т.е. линейный по размеру массива.

Мне понадобилось пару часов, чтобы разобраться с этим - я бы не хотел придумывать это под давлением интервью! Если я сделал буфу, я слишком устал, чтобы заметить это ...

Э-э ... Я выбираю определение "однопроходного", как один проход по матрице, а не касание каждого значения один раз! : -)

#include <stdio.h>
#include <memory.h>

#define SIZE    5

typedef unsigned char u8;

u8 g_Array[ SIZE ][ SIZE ];

void Dump()
{
    for ( int nRow = 0; nRow < SIZE; ++nRow )
    {
        for ( int nColumn = 0; nColumn < SIZE; ++nColumn )
        {
            printf( "%d ", g_Array[ nRow ][ nColumn ] );
        }
        printf( "\n" );
    }
}

void Process()
{
    u8 fCarriedAlpha = true;
    u8 fCarriedBeta = true;
    for ( int nStep = 0; nStep < SIZE; ++nStep )
    {
        u8 fAlpha = (nStep > 0) ? g_Array[ nStep-1 ][ nStep ] : true;
        u8 fBeta = (nStep > 0) ? g_Array[ nStep ][ nStep - 1 ] : true;
        fAlpha &= g_Array[ nStep ][ nStep ];
        fBeta &= g_Array[ nStep ][ nStep ];
        g_Array[ nStep-1 ][ nStep ] = fCarriedBeta;
        g_Array[ nStep ][ nStep-1 ] = fCarriedAlpha;
        for ( int nScan = nStep + 1; nScan < SIZE; ++nScan )
        {
            fBeta &= g_Array[ nStep ][ nScan ];
            if ( nStep > 0 )
            {
                g_Array[ nStep ][ nScan ] &= g_Array[ nStep-1 ][ nScan ];
                g_Array[ nStep-1][ nScan ] = fCarriedBeta;
            }

            fAlpha &= g_Array[ nScan ][ nStep ];
            if ( nStep > 0 )
            {
                g_Array[ nScan ][ nStep ] &= g_Array[ nScan ][ nStep-1 ];
                g_Array[ nScan ][ nStep-1] = fCarriedAlpha;
            }
        }

        g_Array[ nStep ][ nStep ] = fAlpha & fBeta;

        for ( int nScan = nStep - 1; nScan >= 0; --nScan )
        {
            g_Array[ nScan ][ nStep ] &= fAlpha;
            g_Array[ nStep ][ nScan ] &= fBeta;
        }
        fCarriedAlpha = fAlpha;
        fCarriedBeta = fBeta;
    }
}

int main()
{
    memset( g_Array, 1, sizeof(g_Array) );
    g_Array[0][1] = 0;
    g_Array[0][4] = 0;
    g_Array[1][0] = 0;
    g_Array[1][4] = 0;
    g_Array[3][1] = 0;

    printf( "Input:\n" );
    Dump();
    Process();
    printf( "\nOutput:\n" );
    Dump();

    return 0;
}

Answer 8

вот мое решение. Как вы можете видеть из кода, учитывая матрицу M * N, он устанавливает всю строку в ноль, как только проверяет ноль в этой строке. Временная сложность моего решения - O (M * N). Я делюсь всем классом, который имеет статический заполненный массив для тестирования и метод отображения, чтобы увидеть результат в консоли.

public class EntireRowSetToZero {
    static int arr[][] = new int[3][4];
    static {

    arr[0][0] = 1;
    arr[0][1] = 9;
    arr[0][2] = 2;
    arr[0][3] = 2;

    arr[1][0] = 1;
    arr[1][1] = 5;
    arr[1][2] = 88;
    arr[1][3] = 7;

    arr[2][0] = 0;
    arr[2][1] = 8;
    arr[2][2] = 4;
    arr[2][3] = 4;
}

public static void main(String[] args) {
    displayArr(EntireRowSetToZero.arr, 3, 4);
    setRowToZero(EntireRowSetToZero.arr);
    System.out.println("--------------");
    displayArr(EntireRowSetToZero.arr, 3, 4);


}

static int[][] setRowToZero(int[][] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr[i].length; j++) {
            if(arr[i][j]==0){
                arr[i]=new int[arr[i].length];
            }
        }

    }
    return arr;
}

static void displayArr(int[][] arr, int n, int k) {

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < k; j++) {
            System.out.print(arr[i][j] + " ");
        }
        System.out.println("");
    }

}

}

Answer 9

надеюсь, вам понравится мое 1-проходное решение c #

вы можете получить элемент с O (1) и нужно только пространство одной строки и одного столбца матрицы

bool[][] matrix =
{
    new[] { true, false, true, true, false }, // 10110
    new[] { false, true, true, true, false }, // 01110
    new[] { true, true, true, true, true },   // 11111
    new[] { true, false, true, true, true },  // 10111
    new[] { true, true, true, true, true }    // 11111
};

int n = matrix.Length;
bool[] enabledRows = new bool[n];
bool[] enabledColumns = new bool[n];

for (int i = 0; i < n; i++)
{
    enabledRows[i] = true;
    enabledColumns[i] = true;
}

for (int rowIndex = 0; rowIndex < n; rowIndex++)
{
    for (int columnIndex = 0; columnIndex < n; columnIndex++)
    {
        bool element = matrix[rowIndex][columnIndex];
        enabledRows[rowIndex] &= element;
        enabledColumns[columnIndex] &= element;
    }
}

for (int rowIndex = 0; rowIndex < n; rowIndex++)
{
    for (int columnIndex = 0; columnIndex < n; columnIndex++)
    {
        bool element = enabledRows[rowIndex] & enabledColumns[columnIndex];
        Console.Write(Convert.ToInt32(element));
    }
    Console.WriteLine();
}

/*
    00000
    00000
    00110
    00000
    00110
*/

Answer 10

Установите флаг (число, которое выходит за рамки, я использую -1), затем, как только мы изменим все соответствующие строки и столбцы, заменим все флаги на ноль

public class Main {

        public static void main(String[] args) {


            //test case 1
            int[][] multi = new int[][]{
                    { 1, 2, 3 },
                    { 4, 0, 5 },
                    { 0, 6, 7 },
            };

            //test case 2
            int[][] multi2 = new int[][]{
                    { 1, 0, 1, 1, 0 },
                    { 0, 1, 1, 1, 0 },
                    { 1, 1, 1, 1, 1 },
                    { 1, 0, 1, 1, 1},
                    { 1, 1, 1, 1, 1},
            };

            TwoDArraySetZero(multi2);
        }



        static  void  TwoDArraySetZero(int[][] array){

            //iterate through all elements
            for(int i = 0 ; i <= array.length-1 ; i++){
                for (int j = 0; j <= array.length-1; j++) {

                    //checking if match with zero
                    if (array[i][j] == 0){

                        //set replace with -1 all matching zero row and col if not zero
                        for (int k = 0; k <= array.length-1 ; k++) {
                            if(array[i][k] != 0 )
                                array[i][k] = -1;
                            if(array[k][j] != 0)
                                array[k][j]= -1;
                        }
                    }
                }
            }


            //print array
            for(int i = 0; i <= array.length-1; i++)
            {
                for(int j = 0; j <= array.length-1; j++)
                {
                    //replace with zero all -1

                    if(array[i][j] == -1)
                        array[i][j] = 0;

                    System.out.printf("%5d ", array[i][j]);
                }
                System.out.println();
            }

        }

    }