Wyodrębnianie elementów powtarzających się w dwóch tablicach

pytanie zadane 2 kwietnia 2019 w Java przez izas Nowicjusz (120 p.)

Hej! Mam za zadanie napisać program, który wyświetla elementy pojawiające się z tablicy 1, a których nie ma w drugiej. Element o danej wartości ma pojawić się tylko raz.

Doszłam do momentu, w którym te liczby są generowane, ale się powtarzają i naprawdę mimo wielu prób utknęłam chyba na dobre. Dodam, że dopiero zaczynam z Javą i idzie jak po gruzie.

Ważne: nie używamy żadnych innych paczek poza java.lang, przy tym zadaniu mamy też nie tworzyć dodatkowej tablicy.Może ma ktoś pomysł?

import static java.lang.System.out;
public class Task1 {
    public static void main(String[] args) {
    	
    	 	int[] arr = {4,3,4,3,6,7,4,8,2,9};
       		int[] brr = {2,3,6,8,1,5};
            int n = arr.length; 
            int m = brr.length; 
            {
       		
            	System.out.println("The following values of the 1st array do not appear in the 2nd array:");
            	
       		int i;
       		for(i = 0; i < n; i++)
       		{
       			int j;
       		    for(j = 0; j < m; j++)
       		        if(arr[i] == brr[j])
       		        	break;
       		    
       		        if (j == m) {
       		        	     		       		
       		        	System.out.println(arr[i] +" ");  
       		        }
       		}
       		}
    }
}

3 odpowiedzi

odpowiedź 2 kwietnia 2019 przez miro Pasjonat (23,870 p.)

Najłatwiej byłoby z użyciem mapy - wkładasz drugą tablicę w mapę z flagi, a potem pierwszą z innymi, przy czym jak już jest klucz to tej flagi nie zmieniasz. Jednak wydaje mi się, że też map nie można użyć w tym zadaniu.
W takim razie może, posortuj tablice i porównuj elementy z pierwszej tablicy T1 z elementami z drugiej T2, W taki sposób:
- jak el z T1 jest mniejszy niż el z T2 to zwiększ index T1
- jak elementy są równe to zastąp ten z T1 wartością np. Integer.MIN_VALUE, zwiększ index T1
- jak el z T1 jest większy niż el z T2 to zwiększ index T2
Powinno coś z tego wyjść, ale głowy nie dam, ponieważ na szybko to wymyślałem. W tablicy T1 wartości które nie mają Integer.MIN_VALUE to są te szukane.

odpowiedź 3 kwietnia 2019 przez Arkadiusz Fajdek Dyskutant (9,450 p.)

@miro twoja odpowiedź niestety nie jest porpawna. Zauważ że jest warunek w zadaniu

Ważne: nie używamy żadnych innych paczek poza java.lang

Napisałem całe zadanie. Pewnie da się coś ulepszyć, ale myślę że masz elegancki zarys jak to może wyglądać na samych tablicach:

public class DemoApplication {


    public static void main(String[] args) {
		int[] arr = {4,3,4,3,6,7,4,8,2,9};
		int[] brr = {2,3,6,8,1,5};

		Integer[] returnArray = new Integer[arr.length-1];

		for(int i: arr) {
			boolean foundInSecondArray = checkIfNumberIsPresentInArray(brr, i);
			if(!foundInSecondArray) {
				boolean isPresentInReturnArray = checkReturnArray(returnArray, i);
				if(!isPresentInReturnArray) {
					populateReturnArray(returnArray, i);
				}
			}
		}

		for (Integer returnValue : returnArray) {
			if(returnValue != null) System.out.println(returnValue);
		}

	}

	private static void populateReturnArray(Integer[] returnArray, int i) {
		for (int index = 0; index < returnArray.length; index++) {
			Integer returnValue = returnArray[index];
			if(returnValue == null) {
				returnArray[index] = i;
				break;
			}
		}
	}

	private static boolean checkReturnArray(Integer[] returnArray, int i) {
		for (Integer value : returnArray) {
			if(value != null && value == i) {
				return true;
			}
		}
		return false;
	}

	private static boolean checkIfNumberIsPresentInArray(int[] array, int i) {
		for (int value : array) {
			if(value == i) {
				return true;
			}
		}
		return false;
	}

}

komentarz 3 kwietnia 2019 przez Arkadiusz Fajdek Dyskutant (9,450 p.)

@izas Dodatkowo pozwolę sobie podesłać Ci jeden link. Od jakiegoś czasu staram pisać się kurs dla osób początkujących w Javie. Tutaj konkretny link do tablic https://technologicznasowa.pl/struktury-danych-tablice/

Może znajdziesz coś dla siebie! :)

komentarz 3 kwietnia 2019 przez Tomek Sochacki Ekspert (227,510 p.)

@Arkadiusz Fajdek,

Ważne: nie używamy żadnych innych paczek poza java.lang

największa bzdura jaką można sobie wymyślić... a potem dostaje ktoś zadanko do zrobienia na rekrutacji i okazuje się, że po za pętlą for oraz if'em nic nie umie... nie mówiąc już, że dla niektórych zaskoczeniem jest jakie możliwości dają gotowe "narzędzia" dla różnych typów... Bzdura jest uczenie się w taki sposób, szczerze, to jeszcze nie zdarzyło mi się, abym w projekcie jakieś mikrousługi musiał korzystać z tablic takich jak są tutaj (mają zbyt wiele wad w stosunku do lepszych rozwiązań jak listy itp.) czy z takich mnogości pętli for (od tego też są inne metody, znacznie czytelniejsze i przyjemniejsze). Moim zdaniem jak się uczyć to tego, co faktycznie się wykorzysta... ale czasami wydaje mi się, że jestem w tym mysleniu odosobniony...:(

komentarz 3 kwietnia 2019 przez Arkadiusz Fajdek Dyskutant (9,450 p.)

Tomku, ja się z tobą zgadzam w 100%. Ja starałem się odpowiedzieć na oryginalne pytanie, zakładam że to jakieś studenckie (licealne) zadanie, i z tego powodu takie dziwne wymaganie.

Przy użyciu całego dobrodziejstwa Javy to zadanie można by rozwiązać dosłownie w kilka linijek :) Jestem w 100% zwolennikiem wszystkiego co napisałeś, ale na studiach czasem różnie bywa ;) Jak każą robić na tablicach zadanie a Ty użyjesz Seta bo pasuje idealnie to i tak Cie uwalą :)

komentarz 3 kwietnia 2019 przez Tomek Sochacki Ekspert (227,510 p.)

Jestem w 100% zwolennikiem wszystkiego co napisałeś, ale na studiach czasem różnie bywa ;) Jak każą robić na tablicach zadanie a Ty użyjesz Seta bo pasuje idealnie to i tak Cie uwalą :)

dlatego nie warto studiować informatyki, bo często nic ciekawego tam nie uczą... ja nie kończyłem informatyki i w najmniejszym nawet stopniu tego nie żałuję, ba, nawet wiele osób po inf. zgadza się z moją (bardzo negatywną) opinią o poziomie nauczania w polskich uczelniach... (że o technikach już nie wspomnę).

komentarz 3 kwietnia 2019 przez miro Pasjonat (23,870 p.)

Mój drugi sposób nie potrzebuje, żadnych paczek z poza java.lang. Sortowanie można zrobić na tych samych tablicach.

komentarz 4 kwietnia 2019 przez izas Nowicjusz (120 p.)

Zgadzam się z Wami w 100%. Znalazłam już wiele rozwiązań, których niestety przez ograniczenia wykładowcy nie mogłam użyć. Nie mniej nie zaczęłam tych studiów (jestem na 1. semestrze btw) po to, aby zostać programistką, a bardziej po to, aby rozwijać się w pracy, którą już mam. Podoba mi się szperanie w kodzie i będę to robić na własną rękę też poza studiami. :)

Bardzo dziękuję Wam za podpowiedzi, wszystko sobie na spokojnie przeanalizuję.

odpowiedź 3 kwietnia 2019 przez Hexatorn Bywalec (2,240 p.)
edycja 3 kwietnia 2019 przez Hexatorn

Tu masz rozwiązanie zgodne z tym co napisał @miro.
Moim zdaniem jest też o tyle lepsze od rozwiązania od @Arkadiusz Fajdek że mniej razy przechodzisz przez tablice, co przy dużej ilości danych by decydowało o szybkości wykonania operacji.

Samego algorytmu QuickSort nie komentowałem. Jakbyś chciał poznać jak działa to znajdź w google.

public class Main {

    public static void main(String[] args) {

        int[] arr = {4,3,4,3,6,7,4,8,2,9};
        int[] brr = {2,3,6,8,1,5};

        /*System.out.println("Tablica 1 przed posortowaniem:");
        for(int i=0; i<n; i++)
            System.out.print(arr[i]+" ");
        System.out.println("\n");

        System.out.println("Tablica 2 przed posortowaniem:");
        for(int i=0; i<m; i++)
            System.out.print(brr[i]+" ");
        System.out.println("\n");*/

        //sortuje tablice metodą quicksort
        quicksort(arr,0, arr.length-1);
        quicksort(brr,0, brr.length-1);

        /*System.out.println("Tablica 1 po posortowaniu:");
        for(int i=0; i<n; i++)
            System.out.print(arr[i]+" ");
        System.out.println("\n");

        System.out.println("Tablica 2 po posortowaniu:");
        for(int i=0; i<m; i++)
            System.out.print(brr[i]+" ");
        System.out.println("\n");*/


        int loopCounter, jcounter ;
        //Inicjalizacja zmiennych
        //za pomocą loopCounter przechodze po 1 tablicy
        //za pomocą jcounter przechodze po 2 tablicy
        loopCounter = arr.length;
        jcounter = brr.length;

        //W lostOut przechowuje informację o tym jaka wartość została ostatnio zwrócona
        int lastOut = -1;
        //pętla for przechodzi po elementach tablict arr
        for (int i = 0, j=0; i < loopCounter ; i++) {

            //dopuki i wskazuje na większą wartość w tablicy arr niż j w tablicy brr
            //zwiększaj j;
            while (arr[i] > brr[j] && jcounter > j+1){
                j++;
            }
            //sprawdzam czy wartości z tablic arr i brr są równe
            //jeżeli są równe to pomijam dalszą część pętli
            if(arr[i] == brr[j]){
                continue;
            }
            //sprawdzam czy wartości z tablic arr i ostatnio wypisana wartość są równe
            //jeżeli są równe to pomijam dalszą część pętli
            if(arr[i]==lastOut){
                continue;
            }
            //wypisuje wartości
            System.out.print(arr[i]+"\t");
            //przekazuje do przechowania ostatnio wypisaną wartość
            lastOut = arr[i];

        }



    }

    private static void quicksort(int tablica[], int x, int y) {

        int i,j,v,temp;

        i=x;
        j=y;
        v=tablica[(x+y) / 2];
        do {
            while (tablica[i]<v)
                i++;
            while (v<tablica[j])
                j--;
            if (i<=j) {
                temp=tablica[i];
                tablica[i]=tablica[j];
                tablica[j]=temp;
                i++;
                j--;
            }
        }
        while (i<=j);
        if (x<j)
            quicksort(tablica,x,j);
        if (i<y)
            quicksort(tablica,i,y);
    }
}