1
我必須計算來自方陣的幾個子矩陣的和。我有這種格式的輸入：有更快的方法來計算子矩陣的總和嗎？
8 8 // matrix is 8 x 8 and there are going to be 8 submatrixes
-5 -4 -6 -2 1 -8 6 -1 //first row of the matrix
-9 7 -3 -7 2 0 -6 -2 // second row of the matrix etc.
6 -8 2 6 -7 0 3 -5
-1 3 9 4 -7 0 -5 -3
-8 0 0 -6 -5 -7 -7 0
2 7 6 2 -6 6 5 0
-1 -7 8 -7 6 7 -2 1
-8 -3 -5 2 -5 4 -1 -2
0 2 3 6 //upperRow, leftColumn, lowerRow, rightColumn of submatrix
2 6 4 6
0 7 1 7
7 4 7 4
1 7 7 7
2 7 6 7
4 5 6 5
6 2 7 5
我需要計算所有子矩陣的總和（除其他外）。我的代碼工作正常（編譯，運行，給出正確的結果），但我的方法public static int total(int[][] M, int upperRow, int leftColumn, int lowerRow, int rightColumn)殺死所有的表現（我測量它）。確切地說，內部的循環殺死它。
有沒有更快的方式（更有效率）來計算子矩陣的總數？
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map.Entry;
public class Main {
public static void display(int[][] a2d) {
for (int[] a : a2d) {
for (int val : a) {
System.out.print(val + " ");
}
System.out.println();
}
}
public static int total(int[][] M, int upperRow, int leftColumn, int lowerRow, int rightColumn) {
int rows = lowerRow - upperRow + 1;
int cols = rightColumn - leftColumn + 1;
int sum = 0;
int columnToCopyFrom = leftColumn;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
sum += M[upperRow][columnToCopyFrom];
columnToCopyFrom++;
}
columnToCopyFrom = leftColumn;
upperRow++;
}
return sum;
}
public static void main(String[] args) throws Exception {
//BufferedReader br = new BufferedReader(new FileReader("input3"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] firstLine = br.readLine().split(" ");
int n = Integer.parseInt(firstLine[0]);
int k = Integer.parseInt(firstLine[1]);
int[][] M = new int[n][n];
for (int i = 0; i < n; i++) {
String[] rowContents = br.readLine().split(" ");
for (int j = 0; j < rowContents.length; j++) {
M[i][j] = Integer.parseInt(rowContents[j]);
}
}
int avgSum = 0;
int total;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < k; i++) {
String[] rowContents = br.readLine().split(" ");
int upperRow = Integer.parseInt(rowContents[0]);
int leftColumn = Integer.parseInt(rowContents[1]);
int lowerRow = Integer.parseInt(rowContents[2]);
int rightColumn = Integer.parseInt(rowContents[3]);
total = total(M, upperRow, leftColumn, lowerRow, rightColumn);
//srednia
avgSum += total;
//klasy abstrakcji
if (!map.containsKey(total)) {
map.put(total, 1);
} else {
map.put(total, map.get(total) + 1);
}
//display(cutOut);
}
int maxCount = 0;
int maxAbstractionClass = Integer.MIN_VALUE;
ArrayList<Entry> list = new ArrayList<Entry>();
for (Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() > maxCount || (entry.getValue() == maxCount && entry.getKey() > maxAbstractionClass)) {
maxAbstractionClass = entry.getKey();
maxCount = entry.getValue();
}
}
for (Entry<Integer, Integer> entry : map.entrySet()) {
if(maxCount==entry.getValue()){
list.add(entry);
}
}
System.out.print(map.size() + " " + list.size() + " " + avgSum/k);
}
}
我在HashMap
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map.Entry;
public class Main {
public static HashMap<FourNumbers, Integer> mapOfTotals = new HashMap<FourNumbers, Integer>();
public static void display(int[][] a2d) {
for (int[] a : a2d) {
for (int val : a) {
System.out.print(val + " ");
}
System.out.println();
}
}
public static int total(int[][] M, int upperRow, int leftColumn, int lowerRow, int rightColumn) {
FourNumbers fourNumbers = new FourNumbers(upperRow, leftColumn, lowerRow, rightColumn);
if(mapOfTotals.containsKey(fourNumbers)){
return mapOfTotals.get(fourNumbers);
}
int rows = lowerRow - upperRow + 1;
int cols = rightColumn - leftColumn + 1;
int sum = 0;
int columnToCopyFrom = leftColumn;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
sum += M[upperRow][columnToCopyFrom];
columnToCopyFrom++;
}
columnToCopyFrom = leftColumn;
upperRow++;
}
mapOfTotals.put(fourNumbers, sum);
return sum;
}
public static void main(String[] args) throws Exception {
//BufferedReader br = new BufferedReader(new FileReader("input3"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] firstLine = br.readLine().split(" ");
int n = Integer.parseInt(firstLine[0]);
int k = Integer.parseInt(firstLine[1]);
int[][] M = new int[n][n];
for (int i = 0; i < n; i++) {
String[] rowContents = br.readLine().split(" ");
for (int j = 0; j < rowContents.length; j++) {
M[i][j] = Integer.parseInt(rowContents[j]);
}
}
int avgSum = 0;
int total;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();//KLUCZEM jest nazwa klasy abstrakcji(suma), wartoscia jest liczba wystapien tej klasy abstrakcji
for (int i = 0; i < k; i++) {
String[] rowContents = br.readLine().split(" ");
int upperRow = Integer.parseInt(rowContents[0]);
int leftColumn = Integer.parseInt(rowContents[1]);
int lowerRow = Integer.parseInt(rowContents[2]);
int rightColumn = Integer.parseInt(rowContents[3]);
total = total(M, upperRow, leftColumn, lowerRow, rightColumn);
//srednia
avgSum += total;
//klasy abstrakcji
if (!map.containsKey(total)) {
map.put(total, 1);
} else {
map.put(total, map.get(total) + 1);
}
//display(cutOut);
}
int maxCount = 0;
int maxAbstractionClass = Integer.MIN_VALUE;
ArrayList<Entry> list = new ArrayList<Entry>();
for (Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() > maxCount || (entry.getValue() == maxCount && entry.getKey() > maxAbstractionClass)) {
maxAbstractionClass = entry.getKey();
maxCount = entry.getValue();
}
}
for (Entry<Integer, Integer> entry : map.entrySet()) {
if (maxCount == entry.getValue()) {
list.add(entry);
}
}
System.out.print(map.size() + " " + list.size() + " " + avgSum/k);
}
}
class FourNumbers {
int upperRow, leftColumn, lowerRow, rightColumn;
public FourNumbers(int upperRow, int leftColumn, int lowerRow, int rightColumn) {
this.upperRow = upperRow;
this.leftColumn = leftColumn;
this.lowerRow = lowerRow;
this.rightColumn = rightColumn;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + leftColumn;
result = prime * result + lowerRow;
result = prime * result + rightColumn;
result = prime * result + upperRow;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
FourNumbers other = (FourNumbers) obj;
if (leftColumn != other.leftColumn)
return false;
if (lowerRow != other.lowerRow)
return false;
if (rightColumn != other.rightColumn)
return false;
if (upperRow != other.upperRow)
return false;
return true;
}
}
的[計算在元素之和可能的複製有效的矩陣]（http://stackoverflow.com/questions/2277749/calculate-the-sum-of-elements-in-a-matrix-efficiently） –
@PhamTrung不，不，有，C++解決方案，我需要一個Java解決方案。 – majewa
你需要一個java解決方案，所以你需要在你自己的工作。算法保持不變。當你理解我的鏈接中的概念時，實現很容易。 –