0
Good afternoon, you guys.
I have the following exercise to deliver:
Challenge Mr Milli, Petland City resident, is the famous owner of the world’s largest board game factory.
Recently, he had the idea to launch a new unique board game, which he dubbed the Frequency Board.
The game takes place as follows. Initially, a board with dimensions N N is given containing only 0’s. After that, Q operations are proposed, can be of 4 types:
1 X R: Assign the value R to all numbers in line X;
2 X R: Assign R to all numbers in column X;
3 X: Print the most frequent value in line X;
4 X: Print the most frequent value of column X.
Milli’s not very good with computers, but he’s pretty lazy. Knowing that you are one of the best programmers in the world, it needs your help to solve this problem.
Input The first line of the input consists of two integers N and Q (1 N, Q 105), representing respectively the size of the board and the amount of operations. The next Q lines of the input will contain the Q operations. The first integer of each row will indicate the type of operation. If 1 or 2, it will be followed by two more integers X (1 X N) and R (0 R 50). If 3 or 4, it will be followed by only one more integer X.
Output For each type 3 or 4 operation, your program must produce a line, containing the corresponding response value. If a row or column has two or more values that repeat the same number of times, you should print the largest of them. For example, if a line has the values [5,7,7,2,5,2,1,3], both 2, 5 and 7 repeat twice, then the answer will be 7, as it is the largest of them.
I’m receiving "Your implementation exceeded the running time limit."
I’m probably making this mistake when I count how many occurrences of a number in the array. Thinking of an array of size 100 and that each position has a different value, I believe it is the beginning to try to optimize the code.
I basically hashed "numbers" to receive the values of a row or column. I went through each value of "numbers" within the array. For example, if the value of "numbers" is 0, I am going through the row/column and checking how many occurrences.
I made an arrayFinal matrix receive the number and the counter. In the end it would look something like this:
0 1 2 3 {values in the matrix, not indexes}
2 0 2 1 {occurrence of each value in the matrix}
With this arrayFinal, I walk [2 0 2 1], I find the highest value and make a loop running from last to first. Once I find the occurrence of the highest value I give a break and print the corresponding number. I followed this approach because the Hashset leaves the array "numbers" sorted.
That was the most optimized way I could think of:
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class ex5 {
public static void main(String[] args) {
Scanner ler = new Scanner(System.in);
int N, operacoes;
N = ler.nextInt();
int[][] array = new int[N][N];
preencherMatriz(N, array);
operacoes = ler.nextInt();
ler.nextLine();
while (operacoes > 0) {
String[] op = ler.nextLine().split(" ");
switch (op[0]) {
case "1":
preencherLinha(op[1], op[2], array);
break;
case "2":
preencherColuna(op[1], op[2], array);
break;
case "3":
imprimirFrequenteLinha(op[1], array);
break;
default:
imprimirFrequenteColuna(op[1], array);
break;
}
operacoes--;
}
}
public static void preencherLinha(String a, String b, int[][] array){
int linha = Integer.parseInt(a);
int valor = Integer.parseInt(b);
for (int i = 0; i < array.length; i++) {
array[linha-1][i] = valor;
}
}
public static void preencherColuna(String a, String b, int[][] array) {
int coluna = Integer.parseInt(a);
int valor = Integer.parseInt(b);
for (int i = 0; i < array.length; i++) {
array[i][coluna-1] = valor;
}
}
public static void preencherMatriz(int n, int[][] array){
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
array[i][j] = 0;
}
}
}
public static void imprimirFrequenteLinha(String a, int[][] array){
int linha = Integer.parseInt(a) - 1, count = 0, indice = 0;
Set<Integer> numeros = new HashSet<>();
for (int i = 0; i < array.length; i++) {
numeros.add(array[linha][i]);
}
int n = numeros.size();
int[][] arrayFinal = new int[2][n];
for (Integer valor : numeros) {
for (int i = 0; i < array.length; i++) {
if (valor == array[linha][i]) {
count++;
}
}
arrayFinal[0][indice] = valor;
arrayFinal[1][indice] = count;
count = 0;
indice++;
}
indice = 0;
encontrarMaior(arrayFinal, n);
}
public static void imprimirFrequenteColuna(String a, int[][] array){
int coluna = Integer.parseInt(a) - 1, count = 0, indice = 0;
Set<Integer> numeros = new HashSet<>();
for (int[] ints : array) {
numeros.add(ints[coluna]);
}
int n = numeros.size();
int[][] arrayFinal = new int[2][n];
for (Integer valor : numeros) {
for (int[] ints : array) {
if (valor == ints[coluna]) {
count++;
}
}
arrayFinal[0][indice] = valor;
arrayFinal[1][indice] = count;
count=0;
indice++;
}
indice = 0;
encontrarMaior(arrayFinal, n);
}
public static void encontrarMaior(int[][] array, int n){
int maiorValor = 0;
for (int i = 0; i < n; i++) {
if(array[1][i] > maiorValor){
maiorValor = array[1][i];
}
}
for (int i = n-1; i >= 0; i--) {
if(array[1][i] == maiorValor){
System.out.println(array[0][i]);
break;
}
}
}
}
I was using stream in the print function, but although less verbose I saw that leaves to be desired in performance.
Obs: the challenge is part of an activity of the Digital Innovation One platform. As I stopped on this issue I came to ask for your help...
Any dirt? Below is the example of expected input and output. Thanks to all!
