Tietorakenteet ja algoritmit I
Harjoitus 2

8. Suunnittele huolella algoritmi joka saa parametrinaan kaksi
järjestämätöntä listaa A ja B (ArrayList) ja joka poistaa listasta A
kaikki ne alkiot jotka esiintyvät listassa B. Algoritmi palauttaa
poistettujen alkioiden määrän. Nyt ei siis luoda uutta listaa, vaan
muokataan parametrina saatua. Älä käytä valmiita remove(Object) tai
removeAll() -operaatioita.  Piirrä ensin kuva ongelmasta, sitten
kirjoita ylös ratkaisuperiaate selväsanaisesti suomeksi.  Tämän jälkeen
ala täsmentämään ratkaisuperiaatetta täsmällisemmäksi algoritmiksi 1-3
vaiheessa siten, että lopullinen ratkaisuperiaate on hyvin täsmällisesti
kuvattu ja se on mekaanisesti muutettavissa toimivaksi aliohjelmaksi.
Älä muuta syötelistaa B. Mikä on algoritmisi aikavaativuus? Voisiko sitä
parantaa?

Kuva: A: [5 4 2 4], B: [1 6 2] -> Tulos: A: [5 4 4]

Versio 1:
Käydään A läpi, kutakin alkiota kohti tarkastetaan löytyykö se B:stä,
jos löytyy, niin poistetaan A:sta.

Tarkennuksia versiona 2:

"Löytyykö listasta B": Laitetaan aluksi lista B joukkoon, sitten kunkin
A:n alkion löytymisen tarkastaminen on nopeaa.

"Poistetaan A:sta": Koska A on taulukkopohjainen lista, ei kannata
poistaa remove():lla keskeltä, vaan käyttää .set()-operaatiota ja poistaa vain
lopusta. Sensijaan, että alkio poistetaan keskeltä, _sijoitetaan_
poistettavan alkion tilalle jokin säilytettävä alkio.

Lisää tarkennusta: kun käydään läpi A:ta, ylläpidetään a) tietoa siitä
montako säilytettävää alkiota on sijoitettu listan alkuun
(kirjoituskohta) ja b) tietoa siitä mistä kohtaa alkuperäistä listaa A
nyt luetaan (lukukohta). Kun luetaan kohdasta lukukohta, niin jos se
löytyy B:stä, ei tehdä mitään. Jos sitä ei löydy B:stä, se talletetaan
listan alkuun kohtaan kirjoituskohta (ja siirretään kirjoituskohtaan
eteenpäin).

Versio 3:

Luo uusi joukko BJ listasta B
lukukohta = 0
kirjoituskohta = 0
poistettuja = 0
na = listan A pituus
toista niinkauan kuin lukukohta < na
	jos A[lukukohta] löytyy BJ:stä, niin		
		poistettu++
	muuten
		// säilytetään
		A[kirjoituskohta] = A[lukukohta]
		kirjoituskohta++
	lukukohta++
// poistetetaan lopusta ylimääräiset
toista niin kauan kuin listan A pituus > kirjoituskohta
	poista listan A viimeinen alkio