Java中的稀疏矩阵

Question

稀疏矩阵是其元素主要为零的矩阵。下面的代码使用LinkedLists的ArrayList来实现稀疏矩阵。它定义了一个类Element来存储元素的列号和值。每行由Elements的LinkedList表示，仅具有非零值。很少（如果有的话）行都是零，因此ArrayList用于按升序行的每一行存储LinkedList。

class Element { 
  public int column; 
  public int value; }

public class SparseMatrix { 
  private int mRows; // Number of rows 
  private int mCols; // Number of columns 
  private ArrayList<LinkedList<Element>> mMatrix;

1）如何使用带参数的getter（int r，int c），它提供一定的行和列号来检索矩阵的行和列中的值？

2）如何使用带参数的setter（int r，int c，int v），将r行和c列的值设置为v？ （注意：如果节点不在那里，则必须创建一个新节点。如果v为零，则删除该节点。）

如果我错了请纠正我，但是为了得到矩阵的总行数和列数，我会这样做：

get(int r, int c) {
    int rowSize = mMatrix.length;
    int colSize = mMatrix[0].length;
    }

但是，我不确定如何随后使用它。

Answer 1

我将在这里删除一些基本注释的代码。您应该能够根据您的需要进行调整。我不会使用class Element，因为它持有一个int。价值column的意义无关紧要。

private static int mRows; // Number of rows 
private static int mCols; // Number of columns 
private static final ArrayList<LinkedList<Integer>> mMatrix = new ArrayList<>();


public static void main(String[] args) {
    mRows = 7; //example
    mCols = 4; //example

     //init your matrix
    for (int i = 0; i < mRows; i++) { //add new row 7 times
        mMatrix.add(new LinkedList<>());
        for (int j = 0; j < mCols; j++) {
            mMatrix.get(i).add(0); // add Integer with value 0 (4 times)
        }
    }

    //test
    setValue(5, 3, 159);
    System.out.println(getValue(5, 3));

}

public static void setValue(int r, int c, Integer v) {
    //before call be sure that r < mRows and c < mCols
    mMatrix.get(r).set(c, v); //replaces existing Integer
}

public static Integer getValue(int r, int c) {
    //before call be sure that r < mRows and c < mCols
    return mMatrix.get(r).get(c);
}

Answer 2

我可能不会使用列表，我会在幕后使用Map<Point,T>。

未经测试的代码：

interface Matrix<T> {
    public T get(Point p);
    public void put(Point p, T v);
}

class SparseMatrix<T extends Number> implements Matrix<T> {
    Map<Point,T> map = new HashMap<>();
    @Override
    public T get(Point p) {
        return map.get(p);
    }

    @Override
    public void put(Point p, T v) {
        if ( v.doubleValue() == 0.0) {
            // Any zeros get removed.
            map.remove(p);
        } else {
            map.put(p, v);
        }
    }
}

class Point {
    final int row;
    final int col;

    Point(int row, int col) {
        this.row = row;
        this.col = col;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Point point = (Point) o;

        if (row != point.row) return false;
        return col == point.col;

    }

    @Override
    public int hashCode() {
        int result = row;
        result = 31 * result + col;
        return result;
    }
}