0

age フィールドに基づいて昇順で並べ替えられたクラス Obj の配列があります。O(log (N)) 時間で配列内の指定された最小および最大年齢内の年齢を持つ Obj アイテムの数を見つける必要があります。

名前と年齢の両方が同じ場合にのみ .equals が true になるため、binarySearch を使用できるとは思いません。

これは私がこれまで行ってきたことですが、複雑さが何であるかはわかりません。

public class Obj {
    private String name;
    private int age;

    private Obj(String name, int age) {
        if (name == null) {
             throw new IllegalArgumentException();
        }
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    public boolean equals(Object o) {
        if (!(o instanceof Obj)) {
            return false;
        }

        Obj other = (Obj) o;
        return name.equals(other.getName()) && age == other.getAge();
    }

    public static Obj[] loadFromFile(File f) {
        // Loads from file and returns an array of Obj
    }
}

public static int getObjCountInRange(Obj[] a, int minAge, int maxAge) {
    if(a == null || (minAge < 0 || maxAge < 0) || (minAge > maxAge)) {
        throw new IllegalArgumentException();
    }

    int start = 0;
    for(int i = 0; i < a.length; i++) {
        if(a[i].getAge() >= minAge) {
            start = i;
            break;
        }
    }

    int end = 0;
    for(int i = a.length -1; i > 0; i--) {
        if(a[i].getAge() <= maxAge) {
            end = i;
            break;
        }
    }

    return (end - start) + 1;
}
4

2 に答える 2

0

Comparator を作成し、コンパレータを使用して配列をソートします。

次に、新しい Comparator でコンパレータを取る 2 番目のバイナリ検索シグネチャを使用して、上限と下限を見つけます。

完全一致が得られない場合、負の数が得られます。これは、値が見つかった場合の場所を示し、これを反転すると、境界条件を満たす値の開始/終了の場所が得られます。

于 2013-03-06T10:25:14.027 に答える
0

この質問は、O(logn)実装を提供したhereと同じです。

アイデアは、下限と上限の範囲バイナリ検索によるものです。あなたの例では、すべての値が年齢の値について話しています。

于 2013-12-20T12:55:39.443 に答える