Rozidel mnozin – C / C++ – Fórum – Programujte.com

Zdravim takze mam dve polia o velkosti milion prvkov ..zotriedil som ich vzostupne pomocou QuickSortu a mam urobit ich rozdiel a ten nasledne zapisat do suboru ..este tam nemam algoritmus na odstranenie duplicit ale aj tak mi to tam este vypisuje nejake cisla navyse a neviem si stym rady . dik za pomoc.
Alogoritmus by som popisal takto

Vezmu 1. prvek 1pola , preskakuji (serazene) prvky 2 pola dokud jsou mensi nez 1. prvek 1 pola.
Je-li 1. prvek 1pola odlisny od aktualniho prvku 2 pola , pak patri do rozdilu . V opacnem pripade si musi byt 1. prvek 1 pola aktualni prvek 2 pola rovny - 1. prvek 1pola tedy nepatri do rozdilu.

urobil som to takto

write.open(name);

	int indexFile2 = -1;

	int element;



	for (int indexFile1 = 0; indexFile1 < SIZE; indexFile1++)

	{

		element = field1[indexFile1];

		while ( (indexFile2 < SIZE - 1) && (field2[++indexFile2] < element) );

		if ( indexFile2 >= SIZE - 1)

		{

			for ( int i = indexFile1; i < SIZE; i++)

				write << field1[indexFile1] << endl;

		

			break;

		}

		if ( element != field2[indexFile2])

			write <<  element << endl;

	}

Asi ti neporadím to, co chceš slyšet, ale na tuto úlohu se mi osvědčil binární strom (pokud se rozdílem nemyslí něco jiného). Nesetříděné hodnoty vkládáš do stromu, stejné hodnoty znovu neukládáš. Tím se jich elegantně zbavíš. Následně první strom procházíš inorder a zjišťuješ, jestli není v tom druhém stromu. Když není, tak ukládáš do souboru. Tam dostaneš rozdíl množin v setříděném stavu.

Asi ti neporadím to, co chceš slyšet, ale na tuto úlohu se mi osvědčil binární strom (pokud se rozdílem nemyslí něco jiného). Nesetříděné hodnoty vkládáš do stromu, stejné hodnoty znovu neukládáš. Tím se jich elegantně zbavíš. Následně první strom procházíš inorder a zjišťuješ, jestli není v tom druhém stromu. Když není, tak ukládáš do souboru. Tam dostaneš rozdíl množin v setříděném stavu.

Také jsem zkoušel řešit tuto úlohu. Jednu množinu jsem uložil do binárního vyhledávacího stromu, druhou pouze do pole, které jsem pomocí QuickSort setřídil a následně v něm vyhledával pomocí půlení intervalu a strom jsem procházel in-orderem. Bylo to celkem rychlé.