как найти определенный столбец в 2d массиве, используя разделяй и властвуй

Question

Я пытаюсь решить проблему «разделяй и властвуй», где у меня есть двумерный логический массив, заполненный истиной и ложью. Я пытаюсь найти конкретную колонку, где это только правда. Существует также другой способ найти этот столбец - найти строку, в которой он содержит только 1 истинный индекс, а остальное - ложь. Я должен найти решение меньше, чем O (N ^ 2)

образец массива 2d:

F F T F
F T T T
F F T T
T F T F

Answer 1

Вот решение O (n), возможно, если мы знаем, что хотя бы одна строка содержит только одно истинное значение, и, следовательно, это столбец, который мы ищем.

1. Добавитьиндекс каждого столбца в хэш-набор
2. Для каждой строки просмотрите набор с помощью итератора и выполните следующие действия:
   1. Если вы встретите ложное значение для этого индекса столбца, удалите его из набора.
   2. Если вы встретите истинное значение, установите для логического значения значение true, чтобы вы знали, что это первое столкновение с истинным значением, если вы уже встретили истинное значение, переходите к следующей строке

Единственное значение, оставшееся в наборе, является решением.

Это O (n), потому что 1. это O (n), а 2. это O (n) тоже, так что в целом это O (n) + O (n) = O (n). 2. это O (n), потому что для каждой строки вы смотрите максимум 2 истинных значения (2 - константа), и если вы встретите ложное значение, вы больше не будете смотреть на этот столбец.

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

public class Node {
    public int value;
    public Node next;
    public Node(int value, Node prev) {
        this.value = value;
        if (prev != null)
            prev.next = this;
    }
}

public int getTrueColumn(boolean[][] array) {
    Node head = new Node(0, null);
    Node current = head;
    for (int i = 1; i < array[0].length; i++)
        current = new Node(i, current);
    for (int i = 0; i < array.length; i++) {
        boolean encounteredTrue = false;
        current = head;
        Node prev = null;
        while (current != null) {
            if (array[i][current.value]) {
                if (encounteredTrue)
                    break;
                encounteredTrue = true;
                prev = current;
            } else {
                if (prev == null)
                    head = current.next;
                else
                    prev.next = current.next;
            }
            current = current.next;
        }
    }
    return head.value;   
}