Найти “дыру” в двумерном массиве

374

04 июня 2017, 18:36

Всем привет, я столкнулась с одной задачей и затрудняюсь с написанием кода.Помогите пожалуйста. Дано: Двумерный массив -->

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

Вход: определим что дыра k это когда в строке ее все нули ,а в столбце все 1-ки кроме самого k который равен 0. Выход: существует ли такой k и если да вернуть его значение если нет вернуть -1. Код должен пройти со сложностью O(n). Метод: public static int isSink(int [][] mat)

я написала такой код,но мне сказали что он неверный:

public static int isSink(int[][] mat) {
    int n = mat[0].length;
    boolean[] check = new boolean[n];
    for (int i = 0; i < n; i++)
        check[i] = true;
    for (int i = 0; i < n; i++)
        if (check[i]) {
            for (int j = 0; j < n; j++) {
                if (i != j)
                    check[j] = false;
                else {
                    check[i] = false;
                    break;
                }
                if (i == j)
                    continue;
                if (mat[j][i] == 1)
                    check[j] = false;
                else {
                    check[i] = false;
                    break;
                }
            }
            if (check[i])
                return i;
        }
    return -1;
}

Answer 1

Данный метод работает только для квадратных матриц

public static int isSink(int[][] mat) {
    int rowSum = 0;
    int colSum = 0;
    int colHeight = mat[0].length;
    int rowIndex = -1;
    int colIndex = -1;
    for (int i = 0; i < mat.length; i++) {
        for (int j = 0; j < mat[i].length; j++) {
            // Находи суммы элементов строки(rowSum) и столбца(colSum)
            rowSum += mat[i][j];
            colSum += mat[j][i];
        }
       // Ищем строку в которой все элементы равны 0
       // т.е. сумма элементов, такой строки, равна 0
        if (rowIndex == -1 && rowSum == 0) {
            rowIndex = i;
        } else {
            rowSum = 0;
        }
       // Ищем столбец в котором все элементы, за исключением k, равны 1
       // т.е. сумма элементов, такого столбца, равна (высота столбца - 1)
        if (colIndex == -1 && colSum == colHeight - 1) {
            colIndex = i;
        } else {
            colSum = 0;
        }
    }
    if (rowIndex != -1 && colIndex != -1) {
        System.out.println("The sink is found by row:" + rowIndex + " column:" + colIndex);
        return mat[rowIndex][colIndex];
    }
    return -1;
}