问题描述
n个元素的数组，里面的数都是0~n-1范围内的整数，求数组中任意的一个重复元素，没有重复元素返回-1。
要求
时间复杂度为O(n)，空间复杂度为O(1)
分析
题目数据范围较小（与元素个数相当），容易想到用bitmap或者简单的HASH来处理。但是题目要求空间复杂度为O(1)，所以在做HASH时不能在原数组中简单的用数字来代表元素是否出现或者未出现，因为一旦用特定数字（比如1）来代表该位置i所对应的元素i出现过，那么数组中的第i个元素将会被覆盖，从而导致信息丢失（数组中第i个元素再也无法找回）。这里我们用一个方法来维持相关信息：由于元素的值都是0-n-1范围内的数字，所以当响应元素i出现时，我们可以把arr[i]（arr是指输入的数组）内的元素值改为arr[i]-n，这样当再去取arr[i]的值时，只需要用arr[i]+n即为初始的arr[i]值。当出现了元素i，并且arr[i]的值小于0时（也就是说之前已经出现了i），则i就是一个重复元素。
Read full article from 判断数组中是否有重复元素 - Tristan's blog
No comments:
Post a Comment