0

Bom tarde galera.

Tenho o seguinte exercício para entregar:

Desafio O senhor Milli, morador da cidade Petland, é o famoso proprietário da maior fábrica de jogos de tabuleiros do mundo.

Recentemente, ele teve a ideia de lançar um novo jogo exclusivo de tabuleiro, que ele apelidou de Tabuleiro da Frequência.

O jogo ocorre da seguinte forma. Inicialmente, um tabuleiro com dimensões N × N é dado contendo apenas 0’s. Depois disso, Q operações são propostas, podendo ser de 4 tipos:

1 X R: Atribuir o valor R a todos os números da linha X;

2 X R: Atribuir o valor R a todos os números da coluna X;

3 X: Imprimir o valor mais frequente na linha X;

4 X: Imprimir o valor mais frequente da coluna X.

Milli não é muito bom com computadores, mas é bastante preguiçoso. Sabendo que você é um dos melhores programadores do mundo, ele precisa sua ajuda para resolver este problema.

Entrada A primeira linha da entrada é composta por dois inteiros N e Q (1 ≤ N, Q ≤ 105), representando, respectivamente, o tamanho do tabuleiro e a quantidade de operações. As próximas Q linhas da entrada vão conter as Q operações. O primeiro inteiro de cada linha vai indicar o tipo da operação. Caso seja 1 ou 2, será seguido por mais dois inteiros X (1 ≤ X ≤ N) e R (0 ≤ R ≤ 50). Caso seja 3 ou 4, será seguido por apenas mais um inteiro X.

Saída Para cada operação do tipo 3 ou 4, seu programa deve produzir uma linha, contendo o valor da resposta correspondente. Se uma linha ou coluna tiver dois ou mais valores que se repetem o mesmo número de vezes, você deve imprimir o maior deles. Por exemplo, se uma linha tem os valores [5,7,7,2,5,2,1,3], tanto o 2, 5 e 7 se repetem duas vezes, então a resposta será 7, pois é o maior deles.

Estou recebendo "Sua implementação excedeu o tempo limite de execução."

Provavelmente estou tomando esse erro quanto vou contar quantas ocorrências de um número no array. Pensando em um array de tamanho 100 e que cada posição tenha um valor diferente, creio ser o começo para tentar otimizar o código.

Basicamente fiz um HashSet "numeros" para receber os valores de uma linha ou coluna. Percorri cada valor de "numeros" dentro do array. Por exemplo, se o valor de "numeros" é 0, estou percorrendo a linha/coluna e verificando quantas ocorrências.

Fiz uma matriz arrayFinal receber o número e o contador. No final ficaria algo assim:

0 1 2 3 {valores que estão na matriz, não se trata de índices}

2 0 2 1 {ocorrência de cada valor na matriz}

Com esse arrayFinal, percorro [2 0 2 1], encontro o maior valor e faço um laço percorrendo do último ao primeiro. Assim que encontrar a ocorrência do maior valor dou um break e imprimo o número correspondente. Segui essa abordagem porque o HashSet deixa o array "numeros" ordenado.

Essa foi a forma mais otimizada que consegui pensar:

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;
            }
        }
    }
}

Estava usando stream na função de imprimir, mas apesar de menos verbosa vi que deixa a desejar em performance.

Obs: o desafio faz parte de uma atividade da plataforma Digital Innovation One. Como empaquei nessa questão vim pedir a ajuda de vocês...

Alguma sujestão? Abaixo o exemplo de entrada e saída esperada. Desde já agradeço a todos!

inserir a descrição da imagem aqui

1 Resposta 1

1

Eu não cheguei a importar o seu código no meu editor para debugar mas pode haver dois problemas: a performance pode estar ruim ou você pode ter um loop infinito.

Operações de inserção e busca em listas ou Sets são bastante custosas em termos de desempenho. Notei que em alguns pontos do seu código você tem laços for aninhados.

Minha sugestão de abordagem para descobrir qual é a moda (evento mais frequente, de uma linha ou coluna) é criar um array de 51 posições (índice de 0 a 50) que funciona como contador:

public static void imprimirFrequenteLinha(String a, int[][] array){

    int linha = Integer.parseInt(a) - 1, count = 0, indice = 0;
    // Já que R deve estar no intervalor [0-50], precisamos de 51 posições
    int[] contador = new int[51];

    for (int i = 0; i < array.length; i++) {
        // incrementa o índice do array correspondente ao valor
        contador[ array[linha][i]) ]++;
    }

    int moda = 0;
    for (int i : i < contador.length; i++) {
       // já que em caso de empate devemos usar o número mais alto
       // então devemos usar >= nesta condição
       if (contador[i] >= contador[moda]) {
           moda = i; // nova moda
       }
    }
    System.out.println(moda);
}

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .