【转载】水木算法讨论题
第一题,给一个数组an,数组长度为n,1<=ai<=n,问在o(n)时间复杂度,o(1)空间复杂度,并且不改变数组内容的情况下判断数组中是否出现重复的数据?(提示:利用了数据的冗余位)误区:不能求和来解,版上很多朋友都说求和,然后如果和不是(n*(n+1))/2,那就是表明有重复的,不难举出反例:如:数组{2,2,3,3},有重复的,但数组和是10==(4*(4+1))...