Mallivastaukset, osatehtävä 1: Kokoelmat

Seuraavassa esitetään joukko erilaisia tapoja ratkaista annetut tehtävät. Myös muut ratkaisut ovat mahdollisia.

Osatehtävä 1.1: Duplikaattien poisto

Tehtävänanto

Tee Java-ohjelma PoistaDuplikaatit, joka ottaa mielivaltaisen monta komentoriviparametria, muodostaa niistä joukon, jossa duplikaatit (eli saman arvon toistot) on poistettu ja tulostaa näin syntyneen joukon. Käytä apuna Javan kokoelmaluokkia. Toiminnan voit laittaa suoraan main metodiin.

Ohessa on esimerkki ohjelman mahdollisesta toiminnasta. Huomaa, ettei tulostusjärjestystä ole määrätty.

java PoistaDuplikaatit Jukka Anna Pertti Jaakko Antti Anna Unto Veijo Unto Jukka

[Veijo, Unto, Antti, Anna, Jaakko, Pertti, Jukka]
     

Ratkaisu

Rajapintaluokan java.util.Set dokumentaatiossa todetaan:

A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.

Kannattaa siis käyttää Set-rajapinnan toteuttavaa luokkaa kokoelmana. Koska meidän ei tarvitse järjestää annettuja komentoriviparametrejä, voimme käyttää toteutuksena luokkaa java.util.HashSet. Suoraviivainen toteutus on muodostaa uusi joukko ja for-silmukassa lisätä kukin komentoriviparametri joukkoon. Joukko pitää itse huolta duplikaattien eliminoinnista.

import java.util.Set;
import java.util.HashSet;

public class PoistaDuplikaatit {
    public static void main(String[] args) {
	Set tulos = new HashSet();
	for (int i = 0; i < args.length; i++) {
	    tulos.add(args[i]);
	}
	System.out.println(tulos);
    }
}
      

Tämä ei ole kuitenkaan lyhin mahdollinen ratkaisu. Taulukko voidaan muuttaa suoraan kokoelmaksi luokasta java.util.Arrays löytyvällä staattisella metodilla asList(Object[]). Luokalla java.util.HashSet on luontimetodi, joka ottaa toisen kokoelman ja luo sen pohjalta uuden kokoelman. Saadaan seuraava ratkaisu:

import java.util.Arrays;
import java.util.Set;
import java.util.HashSet;

public class PoistaDuplikaatit {
    public static void main(String[] args) {
	System.out.println(new HashSet(Arrays.asList(args)));
    }
}
      

Kumpi ratkaisu on parempi? Jälkimmäinen on todennäköisesti hitaampi, koska välissä luodaan ylimääräinen kokoelma, joka pitää käydä läpi.

Osatehtävä 1.2: Järjestäminen duplikaatit poistaen

Tehtävänanto

Tee Java-ohjelma Jarjesta1, joka ottaa mielivaltaisen monta komentoriviparametria, muodostaa niistä joukon ja tulostaa ne kasvavassa leksikograafisessa järjestyksessä duplikaatit poistettuna. Käytä apuna Javan kokoelmaluokkia. Toiminnan voit laittaa suoraan main metodiin.

Esimerkki:

java Jarjesta1 Jukka Anna Pertti Jaakko Antti Anna Unto Veijo Unto Jukka

[Anna, Antti, Jaakko, Jukka, Pertti, Unto, Veijo]
     

Ratkaisu

Luokan java.util.TreeSet dokumentaatiossa todetaan:

This class implements the Set interface ... This class guarantees that the sorted set will be in ascending element order, sorted according to the natural order of the elements (see Comparable), or by the comparator provided at set creation time, depending on which constructor is used.

Luokka String toteuttaa TreeSet-kokoelman edellyttämän rajapinnan Comparable. Tehtävän ratkaisu saadaan edellisen kohdan ratkaisusta vaihtamalla luokka HashSet luokaksi TreeSet, joka pitää huolta siitä, että lisätyt merkkijonot ovat järjestyksessä ja duplikaatit on poistettu.

import java.util.Set;
import java.util.TreeSet;

public class Jarjesta1 {
    public static void main(String[] args) {
	Set tulos = new TreeSet();
	for (int i = 0; i < args.length; i++) {
	    tulos.add(args[i]);
	}
	System.out.println(tulos);
    }
}
      

Lyhyempi ratkaisu on:

import java.util.Arrays;
import java.util.Set;
import java.util.TreeSet;

public class Jarjesta1 {
    public static void main(String[] args) {
	System.out.println(new TreeSet(Arrays.asList(args)));
    }
}
      

Osatehtävä 1.3: Järjestäminen duplikaatit säilyttäen

Tehtävänanto

Tee Java-ohjelma Jarjesta2, joka ottaa mielivaltaisen monta komentoriviparametria ja tulostaa ne kasvavassa leksikograafisessa järjestyksessä duplikaatit säilyttäen. Käytä apuna Javan kokoelmaluokkia. Toiminnan voit laittaa suoraan main metodiin.

Esimerkki:

java Jarjesta2 234 aabnm Aa 001 xyz 001a aa Aa 234 123 aabnm

[001, 001a, 123, 234, 234, Aa, Aa, aa, aabnm, aabnm, xyz]
     

Ratkaisu

Koska duplikaatit pitää säilyttää, emme tässä voi käyttää joukkoja. Sopiva kokoelmatyyppi on java.util.List. Edellä mainittu luokan java.util.Arrays staattinen metodi asList palauttaa meille suoraan List-tyyppisen kokoelman, jossa alkiot ovat samassa järjestyksessä kuin parametrina annetussa taulukossa. Lista pitää vielä järjestää. Tähän löytyy ratkaisu luokasta java.util.Collections. Sen metodi sort(List) järjestää annetun listan kasvavaan järjestykseen. Vertailussa käytetään tässä tapauksessa automaattisesti String-luokan metodia compareTo(Object). Saadaan seuraava ratkaisu:

import java.util.Arrays;
import java.util.List;
import java.util.Collections;

public class Jarjesta2 {
    public static void main(String[] args) {
	List l = Arrays.asList(args);
	Collections.sort(l);
	System.out.println(l);
    }
}
      

Osatehtävä 1.4: Järjestäminen duplikaatit säilyttäen

Tehtävänanto

Tehtävä on muuten sama kuin 1.3, mutta tässä järjestyksen pitää olla laskeva. Ohjelman nimi on Jarjesta3.

Esimerkki:

java Jarjesta2 234 aabnm Aa 001 xyz 001a aa Aa 234 123 aabnm

[xyz, aabnm, aabnm, aa, Aa, Aa, 234, 234, 123, 001a, 001]
     

Ratkaisu

Järjestäminen muuhun kuin kasvavaan järjestykseen ei onnistu yhtä suoraviivaisesti kuin edellä. Nyt käytämme luokan Collections toista järjestämismetodia sort(List, Comparator). Rajapinta java.util.Comparator määrittää vertailuolion, jolla on vertailumetodi compare(Object, Object) tietyn tyyppisten olioiden suuruusvertailuun. Meidän pitää siis toteuttaa ko. rajapinta siten, että vertailuoperaatio laittaa oliot laskevaan suuruusjärjestykseen. Tämä tapahtuu seuraavasti:

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Jarjesta3 {
    public static void main(String[] args) {
	List l = Arrays.asList(args);
 	Collections.sort(l, new StringComparator());
 	System.out.println(l);
    }
}

class StringComparator implements Comparator {
    public int compare(Object o1, Object o2) throws ClassCastException {
	String s1 = (String)o1;
	String s2 = (String)o2;
	return -s1.compareTo(s2);
    }
}
      

Määrittelemämme luokka StringComparator määrittää metodin compare niin, että ensin annetut oliot muutetaan String-tyyppisiksi ja näitä verrataan ko. luokan operaatiolla compareTo(Object), mutta tulos käännetään päinvastaiseksi miinusoperaatiolla. Jos annetut parametrit eivät ole tyyppiä String tuottaa tyyppimuunnos poikkeuksen ClassCastException, joka välitetään eteenpäin kutsuvalle metodille, koska metodin compare otsikossa sanotaan throws ClassCastException.

Ratkaisua voidaan tiivistää käyttämällä nimetöntä sisäluokkaa Comparator-olion luomisessa. Voimme kirjoittaa myös compare-metodin hieman tiiviimmin:

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Jarjesta3 {
    public static void main(String[] args) {
	List l = Arrays.asList(args);
	Comparator c = new Comparator() {
		public int compare(Object o1, Object o2) throws ClassCastException {
		    return -((String)o1).compareTo(o2);
		}
	    };
	Collections.sort(l, c);
 	System.out.println(l);
    }
}
      

Kaikkein lyhin ratkaisu saadaan kuitenkin tässä tapauksessa kuitenkin käyttämällä Collections-luokan staattista metodia reverseOrder(), joka tuottaa olioiden luonnolliselle järjestykselle käänteisen järjestyksen. Luonnollinen järjestys on tässä tapauksessa siis luokan String määrittämän metodin compareTo(Object) mukainen.

import java.util.Arrays;
import java.util.List;
import java.util.Collections;

public class Jarjesta3 {
    public static void main(String[] args) {
	List l = Arrays.asList(args);
 	Collections.sort(l, Collections.reverseOrder());
 	System.out.println(l);
    }
}
      

Yllä esitettyjen ratkaisujen lisäksi on mahdollista toimia muuten kuten tehtävässä 1.3, mutta lopuksi kääntää listan järjestys luokan Collections metodilla reverse. Tässä tulee yksi ylimääräinen läpikäynti listalle, mutta se ei haittaa, koska järjestäminen vie kuitenkin valtaosan ajasta.

Osatehtävä 1.5: Suurimman ja pienimmän arvon etsiminen

Tehtävänanto

Tee Java-ohjelma MinMax, joka ottaa mielivaltaisen monta komentoriviparametria, tallettaa ne List-tyyppiseen kokoelmaan ja tulostaa niistä pienimmän ja suurimman. Käytä iteraattoria kokoelman läpikäyntiin ja luokan String metodia compareTo(Object) vertailuun. Toiminnan voit laittaa suoraan main metodiin.

Huom! Tämä ohjelma on jo hieman pitempi kuin aiemmat (voi olla jopa yli 30 riviä)

Esimerkki:

java MinMax Jukka Anna Pertti Jaakko Antti Anna Unto Veijo Unto Jukka

Min = Anna, max = Veijo
     

Ratkaisu

Ratkaisun saisi helposti käyttämällä luokan Collections staattisia metodeja min ja max, mutta se mahdollisuus on tehtävän annossa suljettu pois. Tarkoituksena on käyttää ratkaisussa Iterator-oliota. Seuraavassa on yksi mahdollinen ratkaisu:

import java.util.Iterator;
import java.util.Arrays;
import java.util.List;

public class MinMax {
    public static void main(String[] args) {
	if (args.length != 0) {
	    List l = Arrays.asList(args);
	    Iterator it = l.iterator();
	    String min = (String)it.next();
	    String max = min;
	    while (it.hasNext()) {
		String s = (String)it.next();
		if (min.compareTo(s) > 0) {
		    min = s;
		} else if (max.compareTo(s) < 0) {
		    max = s;
		}
	    }
	    System.out.println("Min = " + min + ", max = " + max);
	} else {
	    System.out.println("Ei komentoriviparametreja");
	}
    }
}
      

Käytämme kahta apumuuttujaa min max. Niille annetaan alkuarvoksi iteraattorin palauttama ensimmäinen arvo. Sitten iteraattorilla otetaan vuorotellen kukin seuraava alkio ja tarkistetaan, onko se pienempi kuin min tai suurempi kuin max ja päivitetään muuttujia sen mukaisesti.