CSES - Etäisyydet 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
    }
}