1

私は Person クラスを持っています:

public class Person implements Comparable<Person> {
    private int id;
    @Override
    public int hashCode() {
        return id;
    }

    @Override
    public boolean equals(Object obj) {
        Person other = (Person) obj;
        return id == other.id;
    }

    @Override
    public int compareTo(Person o) {
        return Integer.compare(id, o.id);
    }
}

そして、私は人のTreeSetを持っています。findPersonById(int id)TreeSetにメソッドを実装する必要があります。

私はこのようにしました：

public Person find(int id) {
    List<Person> personList = new ArrayList(idTreeSet);
    Person pattern = new Person(id);
    int index = Collections.binarySearch(personList, pattern);
    return index < 0 ? null : personList.get(index);
}

現在、find メソッドの効率は O(n) です。これは、TreeSet から ArrayList にすべての要素をコピーする必要があるためです。

しかし、このメソッドを実装するより効率的な方法はありますか?

地図は必要ありません。マップなしで解決することに興味があります。

4

3 に答える 3

3

TreeSetは であるためNavigableSet、 を使用できますTreeSet.subSet。これは、要素の順序に関する知識を利用して、関心のある要素にできるだけ近い要素の範囲を抽出します。

Person pattern = new Person(id);

return
    // Get the Persons between pattern (inclusive) and pattern (inclusive).
    // In other words: all the Persons with id equal to the input,
    // of which there are zero or one.
    idTreeSet.subSet(pattern, true, pattern, true).stream()
        .findFirst()
        .orElse(null);
于 2021-09-16T13:59:01.190 に答える