java - 计算Java中矩阵中未访问的单元格

Question

我有 N x M 矩阵，其中 N 是行数，M 是列数。我必须执行 t 个任务。每个任务包含行、列_1、列_2。这意味着现在访问了给定行的 column_1 到 column_2(含)之间的单元格。

例如:

任务 1:2、3、6 表示单元格 3 到 6 现在已访问第 2 行中的单元格。

假设，我有一个 4 x 4 矩阵，并且有 3 个任务。

任务 1:3,2,3

任务 2:2,1,3

任务 3 : 3 1,3

因此，现在未访问过的单元格数为 10。(任务可以包括以前访问过的单元格数)。

我必须计算未访问的单元格。由于 N 和 M 可以在 1 到 10^9 之间，我无法解决问题。我已经解决了java中N和M较小时的问题，但对于较大的输入无法解决。(任务不会超过1000)

我不是要代码，但任何人都可以给我优化方法来解决这个问题吗？

编辑 1:输入将是这样的(对于给定的示例):

4 4 3

3 2 3

2 1 3

3 1 3

第一行分别表示N M t。因此 N=4、M=4 和 t=3。接下来t行分别显示行column_1 column_2。

Answer 1

在我看来，您必须有某种方式来存储有关已访问单元格的信息，那么为什么不在单元格访问时进行计数呢？在没有看到一些代码示例表单的情况下，我可以提出 2 种方法来计算已访问的单元格。然后，正如其他人所指出的那样，一旦您获得了访问过的单元格计数，获取未访问过的单元格计数应该很简单。

在这两个矩阵中，矩阵都由 3 个类组成:

• 矩阵管理类 - 在这里创建矩阵并获取其元数据
• 矩阵行类 - 在这里存储单元格并实现“访问”逻辑
• Matrix cell 类 - 您的商务舱

第一种方法将在您要求时计算总访问单元格数，复杂度为 O(n)，其中 n 是矩阵中的行数，而第二种方法将在每次新访问时增加访问次数并得到访问次数的复杂度为 O(1)。

我会选择第二种方法，但同样我不知道哪种方法适合您的需求。

首先

Row 类包含一个列表，矩阵中的每一列都有一个单元格，而 Cell 类有一个 boolean 属性，指示该单元格之前是否被访问过。当访问单元格时设置此属性。现在您可以计算连续访问过的单元格数。

用于矩阵操作的示例 MatrixManager 类:

public class MyMatrixManager {    
    private ArrayList<MyRow> matrixRows;

    public void createMatrix(){
        // matrix creation logic
    }

    public void visitCells(int rowIndex, int startColumnIndex, int endColumnIndex){
        MyRow row = matrixRows.get(rowIndex);
        row.visitCells(startColumnIndex, endColumnIndex);
    }

    public int getVisitedCellCount(){
        int visitedCellCount = 0;
        for (MyRow matrixRow : matrixRows) {
            visitedCellCount += matrixRow.getVisitedCellCount();
        }
        return visitedCellCount;
    }
}

表示矩阵中一行的类。这将在每次第一次访问单元格时计数:

public class MyRow {
    private int visitedCellCount;
    private ArrayList<IMyCell> cells;

    public MyRow(ArrayList<IMyCell> cells) {
        this.cells = cells;
        this.visitedCellCount = 0;
    }

    public void visitCells(int startIndex, int endIndex){
        for (int i = startIndex; i <= endIndex; i++) {
            IMyCell cell = cells.get(i);
            if(!cell.isCellVisited()){
                visitedCellCount++; // Count cell visit
            }
            cell.visit();
        }
    }

    public int getVisitedCellCount(){
        return visitedCellCount;
    }   
}

Cell 类的示例接口(interface)。访问方法是您的业务逻辑方法。此接口(interface)的实现应设置 isCellVisisted 属性:

public interface IMyCell {
    public boolean isCellVisited();
    public void visit();
}

不确定遍历 10^9 行对象的性能是否适合您，所以:

第二

为您的所有单元格设置一个计数器。让 Matrix 管理类使用观察者模式记录每次单元格访问:

管理器类的示例，请注意它实现了 ICellVisitListener:

    public class MyMatrixManager implements ICellVisitListener{

    private ArrayList<MyRow> matrixRows;
    private int visitedCellCount;

    public void createMatrix(ArrayList<MyRow> rows){
        // matrix creation logic, Object init..

        // subscribe to events
        for (MyRow row : rows) {
            row.addCellVisitListener(this);
        }
    }

    public void visitCells(int rowIndex, int startColumnIndex, int endColumnIndex){
        MyRow row = matrixRows.get(rowIndex);
        row.visitCells(startColumnIndex, endColumnIndex);
    }

    public int getVisitedCellCount(){
        return visitedCellCount;
    }

    @Override
    public void cellVisitedForFirstTime() {
        visitedCellCount++;
    }    
}

监听器接口(interface)(请注意，您可以更改它，以便它为您提供已访问的单元格对象):

public interface ICellVisitListener {
    void cellVisitedForFirstTime();
}

Row 类现在会在每次第一次访问单元格时引发一个事件:

public class MyRow {
    private List<ICellVisitListener> cellVisitListeners;
    private ArrayList<IMyCell> cells;

    public MyRow2(ArrayList<IMyCell> cells) {
        this.cells = cells;
    }

    public void addCellVisitListener(ICellVisitListener listener){
        cellVisitListeners.add(listener);
    }

    public void removeCellVisitListener(ICellVisitListener listener){
        cellVisitListeners.remove(listener);
    }

    public void visitCells(int startIndex, int endIndex){
        for (int i = startIndex; i <= endIndex; i++) {
            IMyCell cell = cells.get(i);
            if(!cell.isCellVisited()){
                onCellFirstVisit(); // raise event so the visit count is incremented
            }
            cell.visit();
        }
    }

    public void onCellFirstVisit(){
        for (ICellVisitListener listener : cellVisitListeners) {
            listener.cellVisitedForFirstTime();
        }
    }   
}

再次是 IMyCell 界面:

public interface IMyCell {
    public boolean isCellVisited();
    public void visit();
}