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
    Commented 3 июн. 2017 в 15:13
  • А практически какие сложности?
    – 0xdb
    Commented 3 июн. 2017 в 15:30
  • Теоретически я знаю что надо пройти по диагонали если я наталкиваюсь на 0 надо проверить если вся строка это нули,если нет - продолжать дальше пока не столкнусь со строкой где все нули .После я ищу столбик где все 1 кроме k который является нулем в строке которого все нули. Я затрудняюсь в написании кода, а тоесть в построении цикла...Да так чтоб код прошел со сложностью O(n) Commented 3 июн. 2017 в 15:33
  • 1
    @KateYaqoobov надо вычислить суммы элементов столбцов и строк. Пересечение строки сумма элементов которой будет равна 0 и столбеца сумма элементов которого будет равна высота столбца - 1 и дадут индексы элемента k. Для этого будет один проход по всему массиву для вычисления сумм и дальше отдельно проход по вычисленным суммам. В итоге асимптотическая сложность будет O(n)
    – Yuri H
    Commented 3 июн. 2017 в 15:56
  • зачем вычислять сумму элементов? Надо просто пройти по диагонали ,при каждом нахождении нуля проверять строку в которой он находится если там все 0, плюс ко всему надо найти столбик со всеми 1 кроме этого 0 при нахождении такого надо вывести его значение а тоесть k=0 , а если таков не имеется то вывести -1.Таков имеется 4-ый столбик 4-ая строка .Но я затрудняюсь в самом построение цыкла....for...if... Commented 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 методом вычисления суммы элементов столбцов и строк? Commented 3 июн. 2017 в 18:36
  • Куда уж подробней? Пересечение строки, сумма элементов которой будет равна 0, и столбца, сумма элементов которого будет равна высота столбца - 1, и дадут индексы элемента k
    – Yuri H
    Commented 3 июн. 2017 в 18:38
  • Добавил комментарии к примеру кода
    – Yuri H
    Commented 3 июн. 2017 в 18:42
  • тоесть вы суммируете элементы строки и также суммируете элементы столбца?сумма элементов строки должно получиться 0 ... но вот это я не поняла: " и столбеца сумма элементов которого будет равна высота столбца - 1"? Commented 3 июн. 2017 в 18:52
  • 1
    @KateYaqoobov Катя, тем не менее он не прав. И количество образований или работа в Intel это не исправит. Можете ему это смело передать.На счет сложности - можете создать вопрос на этом форуме с моим вариантом решения и спросить это O(n) или O(n*n) вот тогда все и выясните.P.S. для одномерного массива два вложенных цикла означают сложность O(n*n) для двумерного массива(который в Java фактически является массивом из массивов) два цикла значат O(n),так как внешний цикл перебирает ваши массивы, а внутренний элементы в них.Задайте вопрос на форуме, Вам самой будет полезно в этом разобратьс
    – Yuri H
    Commented 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
    Commented 6 дек. 2017 в 3:57
  • @etki, код всегда доберётся до дыры, если она существует. в последней строке все нули, значит в последнем столбце, все кроме одного единицы - т.е. мы в любом случае дойдём либо до последней строки и уйдём до упора вправо по нулям, либо дойдём до столбца с единицами и спустимся в последнюю строку.
    – vp_arth
    Commented 6 дек. 2017 в 3:59
  • @etki, добавил демо на js, можете поиграться со сниппетом. Вы, вероятно забываете, что k для столбца и для строки - это k, по условию.
    – vp_arth
    Commented 6 дек. 2017 в 4:17
  • Не работает ваше решение, если дырка не на диагонали js.do/code/204065 (поменял только тестовые данные) Commented 17 мар. 2018 в 11:18
  • @Виктор, ваши тестовые данные не соответствуют исходному определению задачи. Решение работает, дыр нет.
    – vp_arth
    Commented 17 мар. 2018 в 12:52

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

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