c# - 递归检查数组中是否有重复元素

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