检查数组中是否有任何重复的元素递归

Question

如果整数数组中有任何重复的元素,我必须递归地找到它v.该方法必须具有以下签名:

boolean hasRepeatedElements(int[] v) 

我无法看到任何递归方式,无需为此方法定义另一个方法或至少另一个重载(例如,该方法需要使用后面的元素).首先,我考虑检查当前v是否有一些元素等于第一个元素,然后创建一个包含L-1元素等的新数组,但这看起来效率很低.这是唯一的方法吗？

我在这里错过了什么吗？

Answer 1

我同意递归在这里并不十分必要,但可以使用它.你知道快速排序算法吗？这里可以采取相同的分而治之的方法.

boolean hasRepeatedElements(list v) 
    if v.length <= 1 return false;
    List less, greater;
    x = v[0];
    for each y in v, except v[0]
        if y == x
            return true;
        else if y < x
            less.add(y);
        else if y > x
            greater.add(y);
    end;
    return hasRepeatedElements(less) || hasRepeatedElements(greater);
end;

您还可以添加随机化以使算法统计为O(n*log(n)).

http://en.wikipedia.org/wiki/Quicksort