I hava a question similiar with mege in Python but I am trying to write Java code. Here is my code: The input is: The first line - a number of arrays (k); Each next line - the first number is the array size, next numbers are elements.
Max k is 1024. Max array size is 10*k. All numbers between 0 and 100. Memory limit - 10MB, time limit - 1s. Recommended complexity is k ⋅ log(k) ⋅ n, where n is an array length.
Example input:
4
6 2 26 64 88 96 96
4 8 20 65 86
7 1 4 16 42 58 61 69
1 84
Example output:
1 2 4 8 16 20 26 42 58 61 64 65 69 84 86 88 96 96
I get memory limit errors. I use System.gc() to clear the memory but I recieve timeout error
Here is my code:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class TaskFSolution {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int k = Integer.valueOf(reader.readLine());
short[][] arrays = new short[k][];
int arrayLength = 0;
int[] minPositionInArrays = new int[k];
for (int i = 0; i < k; i++) {
String str = reader.readLine();
String[] elements = str.split(" ");
arrays[i] = new short[Short.valueOf(elements[0]) + 1];
for (int j = 0; j < elements.length; j++) {
arrays[i][j] = Short.valueOf(elements[j]);
}
arrayLength += Short.valueOf(elements[0]);
minPositionInArrays[i] = 1;
if (arrayLength % 100 == 0) {
System.gc();
}
}
reader.close();
StringBuilder sb = new StringBuilder();
int currentArrayNumber = 0;
int currentPositionInArray = minPositionInArrays[currentArrayNumber];
while (arrayLength > 0) {
short currentMinValue = 101;
for (int i = 0; i < k; i++) {
if (minPositionInArrays[i] <= arrays[i][0] && currentMinValue >= arrays[i][minPositionInArrays[i]]) {
currentMinValue = arrays[i][minPositionInArrays[i]];
currentArrayNumber = i;
currentPositionInArray = minPositionInArrays[i] + 1;
}
}
sb.append(currentMinValue + " ");
minPositionInArrays[currentArrayNumber] = currentPositionInArray;
arrayLength--;
}
System.out.println(sb.toString().trim());
}
}
1
, but 2x a96
in the output? \$\endgroup\$