0

我有一个基于年龄字段按升序排序的类 Obj 数组。我需要在 O(log (N)) 时间的数组中找到年龄在给定的最小和最大年龄范围内的 Obj 项目的数量。

我认为我不能使用 binarySearch，因为 .equals 仅在名称和年龄相同时才成立。

这是我到目前为止所做的，但我不确定复杂性是什么。

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

编写一个比较器并使用比较器对数组进行排序。

然后使用第二个二进制搜索签名，该签名将比较器与您的新比较器一起查找您的上限和下限。

如果您没有得到完全匹配，您将得到一个负数，这表示如果找到您的值，将其反转，您将获得满足边界条件的值的开始/结束位置。

于 2013-03-06T10:25:14.027 回答
0

这个问题与此处相同，我在此处给出了O(logn)实现。

这个想法是通过范围二进制搜索来寻找下限和上限。对于您的示例，所有值都在谈论年龄值。

于 2013-12-20T12:55:39.443 回答