3

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

                     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;
}
7
  • В чём конкретно возникли затруднения?
    – 0xdb
    3 июн 2017 в 15:13
  • А практически какие сложности?
    – 0xdb
    3 июн 2017 в 15:30
  • Теоретически я знаю что надо пройти по диагонали если я наталкиваюсь на 0 надо проверить если вся строка это нули,если нет - продолжать дальше пока не столкнусь со строкой где все нули .После я ищу столбик где все 1 кроме k который является нулем в строке которого все нули. Я затрудняюсь в написании кода, а тоесть в построении цикла...Да так чтоб код прошел со сложностью O(n) 3 июн 2017 в 15:33
  • 1
    @KateYaqoobov надо вычислить суммы элементов столбцов и строк. Пересечение строки сумма элементов которой будет равна 0 и столбеца сумма элементов которого будет равна высота столбца - 1 и дадут индексы элемента k. Для этого будет один проход по всему массиву для вычисления сумм и дальше отдельно проход по вычисленным суммам. В итоге асимптотическая сложность будет O(n)
    – Yuri H
    3 июн 2017 в 15:56
  • зачем вычислять сумму элементов? Надо просто пройти по диагонали ,при каждом нахождении нуля проверять строку в которой он находится если там все 0, плюс ко всему надо найти столбик со всеми 1 кроме этого 0 при нахождении такого надо вывести его значение а тоесть k=0 , а если таков не имеется то вывести -1.Таков имеется 4-ый столбик 4-ая строка .Но я затрудняюсь в самом построение цыкла....for...if... 3 июн 2017 в 16:03

2 ответа 2

1

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

public static int isSink(int[][] mat) {
    int rowSum = 0;
    int colSum = 0;
    int colHeight = mat[0].length;

    int iterrationCounter = 0;

    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];
            iterrationCounter++;
        }


        // Ищем строку в которой все элементы равны 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;
        }
    }

    System.err.println(iterrationCounter);

    if (rowIndex != -1 && colIndex != -1) {
        System.out.println("The sink is found by row:" + rowIndex + " column:" + colIndex);
        return mat[rowIndex][colIndex];
    }

    return -1;
}
19
  • обьясните мне пожалуйста более подробно как я прихожу к k методом вычисления суммы элементов столбцов и строк? 3 июн 2017 в 18:36
  • Куда уж подробней? Пересечение строки, сумма элементов которой будет равна 0, и столбца, сумма элементов которого будет равна высота столбца - 1, и дадут индексы элемента k
    – Yuri H
    3 июн 2017 в 18:38
  • Добавил комментарии к примеру кода
    – Yuri H
    3 июн 2017 в 18:42
  • тоесть вы суммируете элементы строки и также суммируете элементы столбца?сумма элементов строки должно получиться 0 ... но вот это я не поняла: " и столбеца сумма элементов которого будет равна высота столбца - 1"? 3 июн 2017 в 18:52
  • 1
    @KateYaqoobov Катя, тем не менее он не прав. И количество образований или работа в Intel это не исправит. Можете ему это смело передать.На счет сложности - можете создать вопрос на этом форуме с моим вариантом решения и спросить это O(n) или O(n*n) вот тогда все и выясните.P.S. для одномерного массива два вложенных цикла означают сложность O(n*n) для двумерного массива(который в Java фактически является массивом из массивов) два цикла значат O(n),так как внешний цикл перебирает ваши массивы, а внутренний элементы в них.Задайте вопрос на форуме, Вам самой будет полезно в этом разобратьс
    – Yuri H
    17 июн 2017 в 10:00
0

Предположим, что дыра существует, и попытаемся её найти.
Для этого пойдём из угла (0, 0) по следующему алгоритму:

if (A[i, j] == 0) i++; else j++;

Мы придём в точку (N, j), т.е. если дыра существует - это определённо дыра k=j.

Теперь, мы можем проверить наличие дыры k за 2 прохода(строка k и столбец k).

Итого, ровно 2 прохода + 1 диагональ для любого размера задачи,
другими словами O(4*N) = O(N)

Демо на javascript:

function check(matrix, k) {
  for (let i = 0; i < matrix.length; ++i) {
    if (matrix[k][i] !== 0) return false;
    if (i!==k && matrix[i][k] == 0) return false
  }
  return true;
}
function solve(matrix) {
  let N = matrix.length;
  let i = 0, j = 0;
  while (i < N && j < N) {
    if (matrix[i][j] == 0) j++;
    else i++;
  }
  if (i < N && check(matrix, i)) return i;
  else return -1;
}

console.log(solve([
  [0, 0, 1],
  [0, 0, 1],
  [0, 0, 0],
]));

console.log(solve([
    [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]
]));

console.log(solve([
    [0, 1, 0, 1, 1, 0],
    [1, 0, 1, 1, 0, 0],
    [0, 0, 1, 1, 0, 1], 
    [0, 0, 1, 0, 0, 0],
    [1, 0, 1, 1, 0, 0], 
    [0, 1, 0, 1, 1, 1]
]));

10
  • 1
    Что будет, если дыра находится в последней строке, но благодаря предыдущим строкам код до нее просто не доберется?
    – etki
    6 дек 2017 в 3:57
  • @etki, код всегда доберётся до дыры, если она существует. в последней строке все нули, значит в последнем столбце, все кроме одного единицы - т.е. мы в любом случае дойдём либо до последней строки и уйдём до упора вправо по нулям, либо дойдём до столбца с единицами и спустимся в последнюю строку.
    – vp_arth
    6 дек 2017 в 3:59
  • @etki, добавил демо на js, можете поиграться со сниппетом. Вы, вероятно забываете, что k для столбца и для строки - это k, по условию.
    – vp_arth
    6 дек 2017 в 4:17
  • Не работает ваше решение, если дырка не на диагонали js.do/code/204065 (поменял только тестовые данные) 17 мар 2018 в 11:18
  • @Виктор, ваши тестовые данные не соответствуют исходному определению задачи. Решение работает, дыр нет.
    – vp_arth
    17 мар 2018 в 12:52

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.