Установите каждую ячейку в матрице в 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

Хорошо, я устал, так как сейчас 3 часа ночи, но у меня есть первая попытка на месте с ровно 2 проходами на каждое число в матрице, поэтому в O (NxN) он линейный по размеру матрицы.

Я использую 1-й столбец и первую строку в качестве маркеров, чтобы знать, где находятся строки / столбцы только с 1. Затем есть 2 переменные l и c, которые нужно запомнить, если 1-я строка / столбец тоже все 1. Таким образом, первый проход устанавливает маркеры и сбрасывает остальные на 0.

Второй проход устанавливает 1 в местах, где строки и столбцы отмечены как 1, и сбрасывает 1-ю строку / столбец в зависимости от l и c.

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

import pprint

m = [[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]]



N = len(m)

### pass 1

# 1 rst line/column
c = 1
for i in range(N):
    c &= m[i][0]

l = 1
for i in range(1,N):
    l &= m[0][i]


# other line/cols
# use line1, col1 to keep only those with 1
for i in range(1,N):
    for j in range(1,N):
        if m[i][j] == 0:
            m[0][j] = 0
            m[i][0] = 0
        else:
            m[i][j] = 0

### pass 2

# if line1 and col1 are ones: it is 1
for i in range(1,N):
    for j in range(1,N):
        if m[i][0] & m[0][j]:
            m[i][j] = 1

# 1rst row and col: reset if 0
if l == 0:
    for i in range(N):
        m [i][0] = 0

if c == 0:
    for j in range(1,N):
        m [0][j] = 0


pprint.pprint(m)

Answer 2

Это невозможно сделать за один проход, так как один бит влияет на биты до и после него в любом порядке. IOW. В каком бы порядке вы ни проходили массив, позже вы можете встретить 0, что означает, что вы должны вернуться назад и изменить предыдущее 1 на 0.

Обновление

Люди, кажется, думают, что, ограничив N некоторым фиксированным значением (скажем, 8), вы можете решить, что это один проход. Ну, это а) упущение и б) не оригинальный вопрос. Я бы не стал публиковать вопрос о сортировке и ожидать ответа, который начинался бы "предполагая, что вы хотите отсортировать только 8 вещей ...".

Тем не менее, это разумный подход, если вы знаете, что N фактически ограничено 8. Мой ответ выше отвечает на первоначальный вопрос, который не имеет такого отступления.

Answer 3

Таким образом, моя идея состоит в том, чтобы использовать значения в последней строке / столбце в качестве флага, чтобы указать, являются ли все значения в соответствующем столбце / строке 1с.

Использование сканирования Zig Zag по всей матрице, КРОМЕ конечной строки / столбца. В каждом элементе вы устанавливаете значение в последней строке / столбце как логическое И для самого себя со значением в текущем элементе. Другими словами, если вы нажмете 0, последняя строка / столбец будет установлен на 0. Если вы это 1, значение в последней строке / столбце будет 1, только если оно уже было 1. В любом случае установите текущий элемент на 0.

Когда вы закончите, ваша последняя строка / столбец будет иметь 1 с, если соответствующий столбец / строка была заполнена 1 с.

Выполните линейное сканирование последней строки и столбца и найдите 1 с. Установите 1 в соответствующие элементы в теле матрицы, где последняя строка и столбец равны 1 с.

Кодирование будет непростым, чтобы избежать случайных ошибок и т. Д., Но оно должно работать за один проход.

Answer 4

У меня есть решение, оно выполняется за один проход и выполняет всю обработку «на месте» без дополнительной памяти (за исключением увеличения стека).

Он использует рекурсию для задержки записи нулей, что, конечно, разрушит матрицу для других строк и столбцов:

#include <iostream>

/**
* The idea with my algorithm is to delay the writing of zeros
* till all rows and cols can be processed. I do this using
* recursion:
* 1) Enter Recursive Function:
* 2) Check the row and col of this "corner" for zeros and store the results in bools
* 3) Send recursive function to the next corner
* 4) When the recursive function returns, use the data we stored in step 2
*       to zero the the row and col conditionally
*
* The corners I talk about are just how I ensure I hit all the row's a cols,
* I progress through the matrix from (0,0) to (1,1) to (2,2) and on to (n,n).
*
* For simplicities sake, I use ints instead of individual bits. But I never store
* anything but 0 or 1 so it's still fair ;)
*/

// ================================
// Using globals just to keep function
// call syntax as straight forward as possible
int n = 5;
int m[5][5] = {
                { 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 }
            };
// ================================

// Just declaring the function prototypes
void processMatrix();
void processCorner( int cornerIndex );
bool checkRow( int rowIndex );
bool checkCol( int colIndex );
void zeroRow( int rowIndex );
void zeroCol( int colIndex );
void printMatrix();

// This function primes the pump
void processMatrix() {
    processCorner( 0 );
}

// Step 1) This is the heart of my recursive algorithm
void processCorner( int cornerIndex ) {
    // Step 2) Do the logic processing here and store the results
    bool rowZero = checkRow( cornerIndex );
    bool colZero = checkCol( cornerIndex );

    // Step 3) Now progress through the matrix
    int nextCorner = cornerIndex + 1;
    if( nextCorner < n )
        processCorner( nextCorner );

    // Step 4) Finially apply the changes determined earlier
    if( colZero )
        zeroCol( cornerIndex );
    if( rowZero )
        zeroRow( cornerIndex );
}

// This function returns whether or not the row contains a zero
bool checkRow( int rowIndex ) {
    bool zero = false;
    for( int i=0; i<n && !zero; ++i ) {
        if( m[ rowIndex ][ i ] == 0 )
            zero = true;
    }
    return zero;
}

// This is just a helper function for zeroing a row
void zeroRow( int rowIndex ) {
    for( int i=0; i<n; ++i ) {
        m[ rowIndex ][ i ] = 0;
    }
}

// This function returns whether or not the col contains a zero
bool checkCol( int colIndex ) {
    bool zero = false;
    for( int i=0; i<n && !zero; ++i ) {
        if( m[ i ][ colIndex ] == 0 )
            zero = true;
    }

    return zero;
}

// This is just a helper function for zeroing a col
void zeroCol( int colIndex ) {
    for( int i=0; i<n; ++i ) {
        m[ i ][ colIndex ] = 0;
    }
}

// Just a helper function for printing our matrix to std::out
void printMatrix() {
    std::cout << std::endl;
    for( int y=0; y<n; ++y ) {
        for( int x=0; x<n; ++x ) {
            std::cout << m[y][x] << " ";
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
}

// Execute!
int main() {
    printMatrix();
    processMatrix();
    printMatrix();
}

Answer 5

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

Answer 6

проблема может быть решена за один проход

сохранение матрицы в массиве i X j.

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

one each pass save the values of i and j for an element which is 0 in arrays a and b
when first row is scanned a= 1 b = 2,5
when second row is scanned a=1,2 b= 1,2,5
when third row is scanned no change
when fourth row is scanned a= 1,2,4 and b= 1,2,5
when fifth row is scanned no change .

теперь выведите все значения как 0 для значений i и j, сохраненных в a и b остальные значения равны 1, то есть (3,3) (3,4) (5,3) и (5,4)

Answer 7

Я могу сделать это с двумя целочисленными переменными и двумя проходами (до 32 строк и столбцов ...)

bool matrix[5][5] = 
{ 
    {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}
};

int CompleteRows = ~0;
int CompleteCols = ~0;

// Find the first 0
for (int row = 0; row < 5; ++row)
{
    for (int col = 0; col < 5; ++col)
    {
        CompleteRows &= ~(!matrix[row][col] << row);
        CompleteCols &= ~(!matrix[row][col] << col);
    }
}

for (int row = 0; row < 5; ++row)
    for (int col = 0; col < 5; ++col)
        matrix[row][col] = (CompleteRows & (1 << row)) && (CompleteCols & (1 << col));

Answer 8

Сохраняйте единственную переменную, чтобы отслеживать, каковы все строки ANDed вместе.

Если строка равна -1 (все 1 с), то сделайте следующую строку ссылкой на эту переменную

Если строка - это что-то кроме, это - 0. Вы можете сделать все за один проход. Псевдопользователей-код:

foreach (my $row) rows {
     $andproduct = $andproduct & $row;
     if($row != -1) {
        zero out the row
     }  else {
        replace row with a reference to andproduct
     }
}

Это должно быть сделано за один проход - но здесь есть предположение, что N достаточно мало, чтобы процессор выполнял арифметику в одной строке, иначе вам придется циклически проходить по каждой строке, чтобы определить если это все 1 или нет, я верю. Но учитывая, что вы спрашиваете об алгоритмах и не ограничиваете мое оборудование, я бы просто начал свой ответ с «Построить процессор, который поддерживает N-битную арифметику ...»

Вот один пример того, как это можно сделать на C. Примечание. Я утверждаю, что значения и arr, взятые вместе, представляют массив, а p и numproduct - это мои итераторы и переменные продукта AND, используемые для реализации проблемы. (Я мог зациклить arr с арифметикой указателя, чтобы проверить мою работу, но одного раза было достаточно!)

int main() {
    int values[] = { -10, 14, -1, -9, -1 }; /* From the problem spec, converted to decimal for my sanity */
    int *arr[5] = { values, values+1, values+2, values+3, values+4 };
    int **p;
    int numproduct = 127;

    for(p = arr; p < arr+5; ++p) {
        numproduct = numproduct & **p;
        if(**p != -1) {
            **p = 0;
        } else {
            *p = &numproduct;
        }
    }

    /* Print our array, this loop is just for show */
    int i;
    for(i = 0; i < 5; ++i) {
        printf("%x\n",*arr[i]);
    }
    return 0;
}

Это дает 0, 0, 6, 0, 6, что является результатом для заданных входных данных.

Или в PHP, если люди думают, что мои стековые игры на C читерские (я предлагаю вам, чтобы это было не так, потому что я должен иметь возможность хранить матрицу любым удобным для меня способом):

<?php

$values = array(-10, 14, -1, -9, -1);
$numproduct = 127;

for($i = 0; $i < 5; ++$i) {
    $numproduct = $numproduct & $values[$i];
    if($values[$i] != -1) {
        $values[$i] = 0;
    } else {
        $values[$i] = &$numproduct;
    }
}

print_r($values);

Я что-то упустил?

Answer 9

Другое решение , которое занимает два прохода, заключается в накоплении AND по горизонтали и вертикали:

1 0 1 1 0 | 0
0 1 1 1 0 | 0
1 1 1 1 1 | 1
1 0 1 1 1 | 0
1 1 1 1 1 | 1
----------+
0 0 1 1 0    

Я думал, что смогу разработать такой алгоритм, используя биты четности , Коды Хэмминга или динамическое программирование , возможно, используя эти два логических значения в качестве 2-битного числа , но я пока не добился успеха.

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

Answer 10

Хороший вызов. Это решение использует только два логических значения, созданных в стеке, но логические значения создаются несколько раз в стеке, поскольку функция является рекурсивной.

typedef unsigned short     WORD;
typedef unsigned char      BOOL;
#define true  1
#define false 0
BYTE buffer[5][5] = {
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
};
int scan_to_end(BOOL *h,BOOL *w,WORD N,WORD pos_N)
{
    WORD i;
    for(i=0;i<N;i++)
    {
        if(!buffer[i][pos_N])
            *h=false;
        if(!buffer[pos_N][i])
            *w=false;
    }
    return 0;
}
int set_line(BOOL h,BOOL w,WORD N,WORD pos_N)
{
    WORD i;
    if(!h)
        for(i=0;i<N;i++)
            buffer[i][pos_N] = false;
    if(!w)
        for(i=0;i<N;i++)
            buffer[pos_N][i] = false;
    return 0;
}
int scan(int N,int pos_N)
{
    BOOL h = true;
    BOOL w = true;
    if(pos_N == N)
        return 0;
    // Do single scan
    scan_to_end(&h,&w,N,pos_N);
    // Scan all recursive before changeing data
    scan(N,pos_N+1);
    // Set the result of the scan
    set_line(h,w,N,pos_N);
    return 0;
}
int main(void)
{
    printf("Old matrix\n");
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[0][0],(WORD)buffer[0][1],(WORD)buffer[0][2],(WORD)buffer[0][3],(WORD)buffer[0][4]);
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[1][0],(WORD)buffer[1][1],(WORD)buffer[1][2],(WORD)buffer[1][3],(WORD)buffer[1][4]);
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[2][0],(WORD)buffer[2][1],(WORD)buffer[2][2],(WORD)buffer[2][3],(WORD)buffer[2][4]);
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[3][0],(WORD)buffer[3][1],(WORD)buffer[3][2],(WORD)buffer[3][3],(WORD)buffer[3][4]);
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[4][0],(WORD)buffer[4][1],(WORD)buffer[4][2],(WORD)buffer[4][3],(WORD)buffer[4][4]);
    scan(5,0);
    printf("New matrix\n");
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[0][0],(WORD)buffer[0][1],(WORD)buffer[0][2],(WORD)buffer[0][3],(WORD)buffer[0][4]);
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[1][0],(WORD)buffer[1][1],(WORD)buffer[1][2],(WORD)buffer[1][3],(WORD)buffer[1][4]);
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[2][0],(WORD)buffer[2][1],(WORD)buffer[2][2],(WORD)buffer[2][3],(WORD)buffer[2][4]);
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[3][0],(WORD)buffer[3][1],(WORD)buffer[3][2],(WORD)buffer[3][3],(WORD)buffer[3][4]);
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[4][0],(WORD)buffer[4][1],(WORD)buffer[4][2],(WORD)buffer[4][3],(WORD)buffer[4][4]);
    system( "pause" );
    return 0;
}

Это сканирует по шаблону как:

s,s,s,s,s
s,0,0,0,0
s,0,0,0,0
s,0,0,0,0
s,0,0,0,0

0,s,0,0,0
s,s,s,s,s
0,s,0,0,0
0,s,0,0,0
0,s,0,0,0

и т. Д.

И затем изменение значений в этом шаблоне при возврате для каждой из функций сканирования. (Снизу вверх):

0,0,0,0,c
0,0,0,0,c
0,0,0,0,c
0,0,0,0,c
c,c,c,c,c

0,0,0,c,0
0,0,0,c,0
0,0,0,c,0
c,c,c,c,c
0,0,0,c,0

и т. Д.