Binary search on distinct values


这是一道在Algorithms 4th Edition上的练习题,原题在P210。1.4.21: Binary search on distinct values. Develop an implementation of binary search for StaticSETofInts (see page 98) where the running time of contains() is guaranteed to be ~ lg R, where R is the number of different integers in the array given as argument to the constructor. 题目意思就是:给定一个大小为N的排好序的数组,可能有重复元素,互异的元素总数是R,设计一个lg R 的算法来查找某个元素。
4E6C.tmp_.jpg
已邀请:

cpcs - 诚实努力

赞同来自: 他人的用化名


看了下那个书上的代码,貌似题目让你改构造函数,让它把重复去掉就可以了。
原来的构造函数
public StaticSETofInts(int[] keys) {

        // defensive copy
        a = new int[keys.length];
        for (int i = 0; i < keys.length; i++)
            a[i] = keys[i];

        // sort the integers
        Arrays.sort(a);

        // check for duplicates
        for (int i = 1; i < a.length; i++)
            if (a[i] == a[i-1])
                throw new IllegalArgumentException("Argument arrays contains duplicate keys.");
 }


修改
public StaticSETofInts(int[] keys) {

        // defensive copy
        int [] b = new int[keys.length];
        for (int i = 0; i < keys.length; i++)
            b[i] = keys[i];

        // sort the integers
        Arrays.sort(b);

        // remove duplicates
        int length = 0;
        for (int i = 0; i < b.length; i++)
            if ((i == 0) || (b[i] != b[length - 1]))
                b[length++] = b[i];
        // no duplications in a[] now.
        a = new int[length];
        for (int i = 0; i < length; i++) 
            a[i] = b[i];
                
    }

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~