Can someone tell me how this code exceeds 256MB? where n is at most 5k.
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.LinkedList;
public class G {
public static void main(String[] args) throws NumberFormatException,
IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
int n = Integer.parseInt(in.readLine());
Point[] E = new Point[n];
HashMap<String, Integer> H = new HashMap<String, Integer>();
String[] N = new String[n * 2];
int index = 0;
for (int i = 0; i < n; i++) {
String[] S = in.readLine().split(" ");
if (!H.containsKey(S[0]))
H.put(S[0], index++);
if (!H.containsKey(S[1]))
H.put(S[1], index++);
int x = H.get(S[0]);
N[x] = S[0];
int y = H.get(S[1]);
N[y] = S[1];
E[i] = new Point(x, y);
}
boolean[][] F = new boolean[index][index];
for (int i = 0; i < n; i++)
F[E[i].x][E[i].y] = F[E[i].y][E[i].x] = true;
short[][] C = new short[index][index];
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
int o1 = -1, o2 = -1;
if (E[i].x == E[j].x) {
o1 = E[i].y;
o2 = E[j].y;
} else if (E[i].x == E[j].y) {
o1 = E[i].y;
o2 = E[j].x;
} else if (E[i].y == E[j].x) {
o1 = E[i].x;
o2 = E[j].y;
} else if (E[i].y == E[j].y) {
o1 = E[i].x;
o2 = E[j].x;
}
if (o1 == -1)
continue;
if (!F[o1][o2]) {
C[o1][o2]++;
C[o2][o1]++;
}
}
out.println(index);
for (int i = 0; i < index; i++) {
int max = Integer.MIN_VALUE;
for (int j = 0; j < index; j++)
max = Math.max(max, C[i][j]);
int cnt = 0;
for (int j = 0; j < index; j++)
if (C[i][j] == max && !F[i][j] && i != j)
cnt++;
out.println(N[i] + " " + cnt);
}
out.flush();
out.close();
}
}
I would be really glad if one of those -ve vote owners actually commented and helped me.
short[][] C = new short[index][index];
boolean[][] F = new boolean[index][index];
index can be at most 10k? So this 2 arrays can use about 290 Mb memory.
Your variable
index
can be at most 10^4. So yourF
andC
2D arrays need approximately 100MB and 200MB (100MB+200MB>256MB) memory space respectively.Thank you :)