3

Estou tentando fazer um algoritmo que ache elementos repetidos em uma matriz qualquer mas não sei como. O algoritmo não deve verificar a repetição só nas linhas ou colunas, e sim na matriz toda (isso que me parece ser o mais complicado).

Alguém poderia dar uma dica de como implementar isso?

3
  • Você já tem algum código de suas tentativas? Se sim, poderia compartilhar conosco?
    – Math
    Commented 20/05/2015 às 13:48
  • Não tenho. Não consegui pensar em alguma maneira de cada elemento ser comparado com todos os outros da matriz. A única coisa que pensei foi em ordenar as linhas e colunas em ordem crescente, aí caso tenha elemento repetido eles vão ficar em posições consecutivas e aí daria pra fazer uma verificação do tipo x == x+1. Mas não consegui implementar assim e achei que teria algum jeito mais simples.
    – Chittolina
    Commented 20/05/2015 às 13:57
  • Algumas destas respostas lhe atenderam?
    – Ricardo
    Commented 13/06/2015 às 13:29

2 Respostas 2

1

Solução dada em pergunta similar em outro site da rede (SOen) Finding repeats in a 2D array

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        int[][] ia = new int[3][3];
        ia[0][0] = 1;
        ia[0][2] = 1;
        ia[0][2] = 1;
        ia[1][0] = 4;
        ia[1][3] = 4;
        ia[1][2] = 2;
        ia[2][0] = 5;
        ia[2][4] = 6;
        ia[2][2] = 7;
        findRepeats(ia, ia.length*ia[0].length);
    }

    public static void findRepeats(int [][] num, int size)
{
    int findNum;
    int total = 1, row = 0, col = 0;
    int [] check = new int[size];
    while(row < num.length && col < num[0].length)
    {
        //Set to number
        findNum = num[row][col];
      //Cycle array to set next number
        if(col < num[0].length-1)
            col++;
        else
        {
            row++;      //Go to next row if no more columns
            col = 0;    //Reset column number
        }
        //Loop through whole array to find repeats
        for(int i = row; i < num.length; i++)
        {
            for(int j = col; j < num[i].length; j++)
            {
                if(num[i][j] == findNum) {
                    total++;
                     //Cycle array to set next number
                      if(col < num[0].length-1)
                          col++;
                      else
                      {
                           row++;      //Go to next row if no more columns
                           col = 0;    //Reset column number
                      }
                      if(row < num.length - 1 && col < num[0].length -1)
                         num[i][j] = num[row][col];
                }
            }
        }


        //Display total repeats
        System.out.println("Number " + findNum + " appears " + total + " times.");
        total = 1;
    }
}
}

Funcionando no ideone

1
  • verdade, Irei atualiza a resposta.
    – Ricardo
    Commented 20/05/2015 às 13:54
1

Para percorrer uma matriz você precisa de um for dentro de um for, logo, uma possível solução é percorrer a matriz e comparar cada elemento percorrendo novamente a matriz. Logo, você terá 4 fors aninhados, sendo que os dois mais externos estão percorrendo a matriz pela primeira vez, e os dois mais internos estão pegando o elemento da iteração externa da matriz e comparando elemento a elemento da iteração interna.

Para aumentar o desempenho da sua comparação, os dois fors mais internos não precisam começar do elemento [0][0], a iteração pode começar a partir do elemento atual da iteração mais externa. Ao encontrar um elemento repetido você armazena esse valor em um ArrayList e continua a iteração mais externa.

Assim:

import java.util.ArrayList;
import java.util.List;

public class Matriz {
    public static void main(String[] args) {
        int[][] matriz = new int[][]{
                {1,2,3,4},
                {3,4,5,6},
                {6,7,8,9}};
        List<Integer> repetidos = new ArrayList<Integer>();

        //percorre a matriz, elemento por elemento
        for(int i=0; i<matriz.length; i++) {
            proximoElemento:
            for(int j=0; j<matriz[i].length; j++) {
                //caso elemento já foi marcado como repetido
                //continua para a próxima iteração
                if(repetidos.contains(matriz[i][j])) continue proximoElemento;

                //percorre novamente a matriz, elemento por elemento
                //começando do elemento atual da iteração mais externa 
                for(int i2=i; i2<matriz.length; i2++) {
                    for(int j2=0; j2<matriz[i2].length; j2++) {
                        //não se compara com ele mesmo
                        if(i==i2 && j==j2) break;
                        //achamos um repetido, armazena e 
                        //continua para a próxima iteração 
                        if(matriz[i][j] == matriz[i2][j2]) {
                            repetidos.add(matriz[i][j]);
                            continue proximoElemento;
                        }
                    }
                }
            }
        }

        //exibe os elementos encontrados repetidos ao menos uma vez
        for(int r: repetidos) {
            System.out.println(r);
        }
    }
}

Resultado:

3
4
6

Exemplo no Ideone

2
  • Não entendi o por quê do i2 ser inicializado como i. Se ele fosse inicializado como 0 o algoritmo funcionaria também, certo?
    – Chittolina
    Commented 20/05/2015 às 18:44
  • @Chittolina certo, também funcionaria, mas é uma otimização que eu fiz para que os fors internos somente percorram os elementos que ainda não foram percorridos pelos fors externos. Isso resulta em um número menor de iterações. Para um exemplo minúsculo como o que eu escrevi não faz muita diferença, mas como eu não sei quantos elementos tem a sua matriz preferi otimizar (pelo menos um pouquinho) o meu código.
    – Math
    Commented 20/05/2015 às 18:45

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 .