「生活可以更简单, 欢迎来到我的开源世界」
  1. 题目一:找出数组中的重复的数字。
  2. 题目二:不修改数组找出重复的数字
面试题3:数组中的重复数字
2020-07-09
」 「

剑指offer面试题3,找数组中的重复数字。

题目一:找出数组中的重复的数字。

在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是重复的数字2或者3。

思路1:对数组进行排序,例如使用快速排序(O(nlgn)),然后对数组进行遍历,判断当前元素与之后的元素是否相等,如果相等即为重复的元素。这种方式简单容易首先想到,但时间复杂度较高。

思路2:使用HashMap,遍历数组然后用O(1)的时间对每个元素判断Map中是否已经包含该元素。如果已经包含,即为重复元素。这种方式的时间复杂度为O(n),但空间复杂度较高为O(n)。

思路3:以上两种方法都没有用到这个数组中的数字在0-n-1范围这一特性,根据这个特性考虑如下思路。因为数组中的元素范围都在0-n-1,因此

从头到尾依次扫描这个数组中每个数字,当扫到下标尾i的数字m时,
如果m等于下标i,则继续扫描下一个元素。
如果不等于,则拿m和下标为m的数字进行比较
如果相等,则说明找到了重复的数字。
如果比较结果不等,就把m和下标为m的数字进行交换
重复以上比较过程,直到发现一个重复的数字。

每个数字最多只要交换两次就能找到属于它的位置,因此时间复杂度是O(n),操作都是在数组上进行的,不需要额外分配内存,空间复杂度为O(1)。
bool duplicate(int numbers[], int length, int* duplication)
{
if(numbers == nullptr || length <= 0)
return false;

for(int i = 0; i < length; ++i)
{
if(numbers[i] < 0 || numbers[i] > length - 1)
return false;
}

for(int i = 0; i < length; ++i)
{
while(numbers[i] != i)
{
if(numbers[i] == numbers[numbers[i]])
{
*duplication = numbers[i];
return true;
}

// 交换numbers[i]和numbers[numbers[i]]
int temp = numbers[i];
numbers[i] = numbers[temp];
numbers[temp] = temp;
}
}

return false;
}

题目二:不修改数组找出重复的数字

在一个长度为n+1的数组里的所有数字都在1~n的范围内,所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字,但不能修改输入的数组。例如,如果输入长度为8的数组{2,3,5,4,3,2,6,7},那么对应的输出是重复的数字2或者3。

思路1:使用辅助数组,逐一遍历原数组,将每个元素作为辅助数组的下标,为辅助数组填1。需要O(n)的辅助空间。

思路2:分而治之策略。将1~n的数字从中间的数字m分为两部分:[1,m]和[m+1,n]。如果前一半区间的数字的在数组中出现的次数超过m,那么该区间肯定含重复的数字。对含重复的区间继续分治,直到查找到一个重复的数字。
int getDuplication(const int* numbers, int length)
{
if(numbers == nullptr || length <= 0)
return -1;

int start = 1;
int end = length - 1;
while(end >= start)
{
int middle = ((end - start) >> 1) + start;
int count = countRange(numbers, length, start, middle);
if(end == start)
{
if(count > 1)
return start;
else
break;
}

if(count > (middle - start + 1))
end = middle;
else
start = middle + 1;
}
return -1;
}

int countRange(const int* numbers, int length, int start, int end)
{
if(numbers == nullptr)
return 0;

int count = 0;
for(int i = 0; i < length; i++)
if(numbers[i] >= start && numbers[i] <= end)
++count;
return count;
}

数组长度为n,则countRange将被调用O(logn)次,每次需要O(n)的时间,所以时间复杂度为O(nlogn),空间复杂度为O(1)。

缺点:不能保证找出所有重复的数字,只能找出任意一个重复的数字。

<⇧>