arrays - 如何使用分治法在二维数组中查找特定列

Question

我正在尝试解决一个分而治之的问题，其中我有一个充满真假的 2d 布尔数组。我试图找到一个特定的列，它是唯一的。还有另一种查找此列的方法是查找仅包含 1 个真实索引而其余为 false 的行。我必须找到小于 O(N^2) 的解决方案

二维数组样本：

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

标签： arraysalgorithmdivide-and-conquer

Answer 1

这是一个 O(n) 的解决方案，如果我们知道至少一行只包含一个真值，那么这就是我们正在寻找的列。

1. 将每个列索引添加到哈希集
2. 对于每一行，使用迭代器遍历集合并执行以下操作：
   1. 如果您遇到该列索引的错误值，请将其从集合中删除。
   2. 如果遇到真值，设置一个布尔值为真，这样你就知道这是第一次遇到真值，如果你已经遇到真值继续下一行

集合中剩余的单个值是解决方案。

这是 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;   
}