Wykrwanie duplikatów numerów w tablicy

Witam,

Piszę program który generuje dwuwymiarową tablicę. Pierwszy wymiar będzie generowany tyle razy ile użytkowanik wpisze, drugi tyle razy ile wygenerowana liczba. Rozmiar tablicy jest stały, ale mam zamiar później ignorować wszystkie wartości z -1.
Teraz tak, elementy w drugim wymiarze nie moga sie powtarzać, i tu jest problem bo nie wiem jak to zrobić. Napisałem metodę CheckRepeatConnections ale niedziała... czy ktoś mógłby mi pomóc?

aha, poki co, do testów pracuję tylko na 1 wymiarze = 0.

z góry dzięki,
Pozdrawiam Piotrek

Kod programu to:

import javax.swing.JOptionPane;
import java.util.*;

public class Network {
	
	String nodes, request;
    int nodes_number, round=1, round_main=1, request_number;
    int Nodes_Array[][];    //declare array
    int tempConnection;

		public void CheckExistingConnections(int node) {
		for (int i = 0; i < node; i++)//loop through previous nodes
		{
			for (int j = 0; j < Nodes_Array.length - 1; j++)
			{
				if (Nodes_Array[i][j] == node) {
					Nodes_Array[node][j] = i;
				}
			}
		}
	}
	
	public void CheckRepeatConnections(int node) { //no repeated connections allowed
		int temp;
		for (int conn = 0; conn < Nodes_Array.length - 1; conn++) {
			temp = Nodes_Array[node][conn];
			for (int k = 0; k < Nodes_Array.length - 1; k++) {
				if (temp == Nodes_Array[node][k] && k != conn)
					Nodes_Array[node][conn] = -2;
			}
		}
	}
	
	public void GenerateConnections() {
		
		for (int node=0; node<Nodes_Array.length; node++){ //loop through nodes
            int numConnections;
            Random rnd  = new Random();
            numConnections = rnd.nextInt(nodes_number - 1) + 1; //+1 so that nodes always has at least 1 connection
            System.out.println("Node = " + node);
            System.out.println("numConnections = " + numConnections);
            
            if (node == 0) //for node 0 randomly make connections
            {
                for (int connection=0; connection < nodes_number - 1; connection++){
                    if(connection >= numConnections){ //make sure we only assign as many connections as we randonly decide to have
                        Nodes_Array[node][connection] = -1;	//if a connection slot is not used, put -1 in it
                    }
                    else{
                    	//tempConnection = rnd.nextInt(nodes_number - 1);
                     

//                        do{
//                            tempConnection = rnd.nextInt(nodes_number -1); 
//                        }
//                        while(tempConnection == node);//if the random number is the same as the current node, make a new one
                    	do{
                            tempConnection = rnd.nextInt(nodes_number -1); 
                            Nodes_Array[node][connection] = tempConnection;
                        }
                        while(tempConnection == node);//if the random number is the same as the current node, make a new one

//                        Nodes_Array[node][connection] = tempConnection;
                    }

                    System.out.println("Connection " + connection + " = " + Nodes_Array[node][connection]);
               }
               CheckRepeatConnections(0);
            }
            else //nodes greater than 0
            {
            	for (int connection=0; connection < nodes_number - 1; connection++){
	                CheckExistingConnections(node);
	                System.out.println("Connection " + connection + " = " + Nodes_Array[node][connection]);
            	}
            }
        }
	}

	public void GetUserInput() {
		//JOptionPane.showMessageDialog(null, "Network generator");
		//user difned number of nodes
	    nodes=JOptionPane.showInputDialog("How many nodes network has?");
	    nodes_number=Integer.parseInt(nodes);
	    //user defined number of connections requests
	    //request=JOptionPane.showInputDialog(null, "How many requests?");
	    // request_number=Integer.parseInt(request);
	    Nodes_Array = new int[nodes_number][nodes_number - 1];//set length of array dimensions
	    for(int i = 0; i < Nodes_Array.length; i++) {
	    	for(int j = 0; j < Nodes_Array.length - 1; j++) {
	    		Nodes_Array[i][j] = -1;
	    	}
	    }
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Network n = new Network();
		n.GetUserInput();
		n.GenerateConnections();
		System.out.println("Exit"); //print to say the program is done
	}

} 

Twój algorytm wykrywania duplikatów działa w czasie O(n^2).

Można to zrobić dużo efektywniej na jeden ze sposób:

1. Posortować tablicę za pomocą Arrays.sort, a następnie przejść całą tablicę i porównywać tylko sąsiednie elementy.
2. Użyć zbioru, np. HashSet. Dla kolejnych elementów tablicy należy dodawać elementy do zbioru za pomocą metody add. Metoda ta będzie miała wartość false jeśli taki element już był.

Btw. W jakim celu robisz taką zawiłą rzecz? Nie mogę zrozumieć przeznaczenia tego kodu. Dużo łatwiej byłoby, gdybyś dla każdego "node" trzymał zbiór połączeń.

widzisz Krzysiek, problem w tym ze nie dziala dlatego ze nadal jestem wstanie dla node = 0 utoworzyc dwa takie same connections.
roznica jest taka, ze jesli dla node 0 wygeneruje 3 connections do node 1, wczesniej pojawialy sie dla node 1 az ttrzy razy a teraz tylko raz, ale to nie do konca o to chodzilo bo jesli sprawdzanie dla 1 node bedzie dzialac, nie bede mial powyzszego (rozwiazanego) problemu.

powodem dlaczego robie to w ten sposob jest fakt iz jesli jesli numConnections zostanie wygenerowany, tyle connections musi zostac przypisanych do node. Czyli jesli numConnections dla node 0 bedzie 3, node 0 musi miec 3 rozne connections.

moje zalozeni jest nastepujace:

1. generuje numConnections = np 3
2. generuje 1 connection
3. generuje 2 connection
4. sprawdzam czy wygenerowane connection juz istanieje

• jesli tak to generuje je jeszcze raz
• jesli nie zapisuje je jako kolejny wolny 2 wymiar

5. generuje kolejne connection itd

jesli bym posortowal tabele, potem posprawdzal sasiednie, musialbym generowac nowe na miejsce usunietych, sprawdzac, sortowac itd.

witam,

wiec udalo mi sie osiagac polowe sukcesu poniewaz program nie generuje juz podwujengo connection. chcialbym tylko zeby program teraz najpierw sprawdzil wszystkie poprzednie conenctions, zapisal je, a potem na miejsce drugiego wymiaru = -1, wygenerowal nowe connections. czy ktos mogly rzucic na to okiem i powiedziec jak to rozwiazac?

z gory dzieki

oto kod:

import javax.swing.JOptionPane;
import java.util.*;

public class Network {
	
	String nodes, request;
    int nodes_number, round=1, round_main=1, request_number;
    int Nodes_Array[][];    //declare array
    int tempConnection;

	public Network() {
		
	}
	
	public void CheckExistingConnections(int node) {
		for (int i = 0; i < node; i++)//loop through previous nodes
		{
			for (int j = 0; j < Nodes_Array.length - 1; j++)
			{
				if (Nodes_Array[i][j] == node) {
					Nodes_Array[node][j] = i;
				}
			}
		}
	}
	
	public boolean isRepeated(int node, int potential) { //no repeated connections allowed

		for (int conn = 0; conn < Nodes_Array[node].length; conn++) {
			if (potential == Nodes_Array[node][conn])
				return true;
		}
		return false;
	}
	
	public void GenerateConnections() {
		
		for (int node=0; node<Nodes_Array.length; node++){ //loop through nodes
            int numConnections;
            Random rnd  = new Random();
            numConnections = rnd.nextInt(nodes_number - 1) + 1; //-1 so that max is num nodes-1, +1 so that nodes always has at least 1 connection
            System.out.println("Node = " + node);
            System.out.println("numConnections = " + numConnections);
            
            if (node == 0) //for node 0 randomly make connections
            {
                for (int connection=0; connection < Nodes_Array[node].length; connection++){
                    if(connection >= numConnections){ //make sure we only assign as many connections as we randonly decide to have
                        Nodes_Array[node][connection] = -1;	//if a connection slot is not used, put -1 in it
                    }
                    else{
                        tempConnection = rnd.nextInt(nodes_number);
                     

                        do{
                            tempConnection = rnd.nextInt(nodes_number); 
//                            System.out.println("looping");
                        }
                        while(tempConnection == node || isRepeated(0, tempConnection));//if the random number is the same as the current node, make a new one


                        Nodes_Array[node][connection] = tempConnection;
                    }
                    System.out.println("Connection " + connection + " = " + Nodes_Array[node][connection]);
               }
            //	randomConnections(node, numConnections);
            }
            else //nodes greater than 0
            {
            	for (int connection=0; connection < nodes_number - 1; connection++){
	                CheckExistingConnections(node);
	                
	                System.out.println("Connection " + connection + " = " + Nodes_Array[node][connection]);
	                
            	}
            	
                //if (Nodes_Array[node][connection] == -1)
                        randomConnections(node, numConnections);
            }
        }
	}
	
	public void randomConnections(int node, int numConnections){
		Random rnd = new Random();
		for (int connection=0; connection < Nodes_Array[node].length; connection++){
            if(connection >= numConnections){ //make sure we only assign as many connections as we randonly decide to have
                Nodes_Array[node][connection] = -1;	//if a connection slot is not used, put -1 in it
            }
            else{
            	tempConnection = rnd.nextInt(nodes_number);
             

                do{
                    tempConnection = rnd.nextInt(nodes_number); 
                    //System.out.println("looping");
                }
                while(tempConnection == node || isRepeated(0, tempConnection));//if the random number is the same as the current node, make a new one


                Nodes_Array[node][connection] = tempConnection;
            }
            System.out.println("Connection " + connection + " = " + Nodes_Array[node][connection]);
       }
	}

	public void GetUserInput() {
		//JOptionPane.showMessageDialog(null, "Network generator");
		//user difned number of nodes
	    nodes=JOptionPane.showInputDialog("How many nodes network has?");
	    nodes_number=Integer.parseInt(nodes);
	    //user defined number of connections requests
	    //request=JOptionPane.showInputDialog(null, "How many requests?");
	    // request_number=Integer.parseInt(request);
	    Nodes_Array = new int[nodes_number][nodes_number - 1];//set length of array dimensions
	    for(int i = 0; i < Nodes_Array.length; i++) {
	    	for(int j = 0; j < Nodes_Array.length - 1; j++) {
	    		Nodes_Array[i][j] = -1;
	    	}
	    }
	}
	
	public static void main(String[] args) {
		Network n = new Network();
		n.GetUserInput();
		n.GenerateConnections();
		System.out.println("Exit"); //print to say the program is done
	}

}