Annettuna on lista, jossa on n eri kokonaislukua. Tehtäväsi on selvittää, mikä on k:nneksi pienin kahden luvun etäisyys, kun tarkastellaan kaikkia mahdollisia lukupareja.

Esimerkiksi kun lista on [4,1,5,2], etäisyydet ovat seuraavat pienimmästä suurimpaan:

• lukujen 1 ja 2 etäisyys on 1
• lukujen 4 ja 5 etäisyys on 1
• lukujen 2 ja 4 etäisyys on 2
• lukujen 1 ja 4 etäisyys on 3
• lukujen 2 ja 5 etäisyys on 3
• lukujen 1 ja 5 etäisyys on 4

Voit olettaa, että n on enintään 10^5, jokainen luku on välillä 1 \dots 10^9 ja k on enintään 10^5.

Python

Toteuta tiedostoon distances.py funktio find, joka palauttaa halutun etäisyyden.

def find(t, k):
    # TODO

if __name__ == "__main__":
    t = [4,1,5,2]
    print(find(t,1)) # 1
    print(find(t,2)) # 1
    print(find(t,3)) # 2
    print(find(t,4)) # 3
    print(find(t,5)) # 3
    print(find(t,6)) # 4

Java

Toteuta tiedostoon Distances.java metodi find, joka palauttaa halutun etäisyyden.

public class Distances {
    public int find(int[] t, int k) {
        // TODO
    }

    public static void main(String[] args) {
        Distances d = new Distances();
        int[] t = {1,2,4,5};
        System.out.println(d.find(t,1)); // 1
        System.out.println(d.find(t,2)); // 1
        System.out.println(d.find(t,3)); // 2
        System.out.println(d.find(t,4)); // 3
        System.out.println(d.find(t,5)); // 3
        System.out.println(d.find(t,6)); // 4
    }
}