【剑指Offer】题3：数组中重复的数字
写在前面的话：
- 版权声明：本文为博主原创文章，转载请注明出处！
- 博主是一个小菜鸟，并且非常玻璃心！如果文中有什么问题，请友好地指出来，博主查证后会进行更正，啾咪~~
- 每篇文章都是博主现阶段的理解，如果理解的更深入的话，博主会不定时更新文章。
- 本文初次更新时间：2021.04.02，最后更新时间：2020.04.02
文章目录
正文开始
题目一：数组中重复的数字
题目描述及分析
题目描述
在一个长度为n的数组里的所有数字都在0~n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。
返回描述
如果数组中有重复的数字，函数返回true，否则返回false。
如果数组中有重复的数字，把重复的数字放到参数duplication[0]中。（ps:duplication已经初始化，可以直接赋值使用。）
知识点：数组
设函数为：
// 参数:
// numbers: 一个整数数组
// length: 数组的长度
// duplication: (输出) 数组中的一个重复的数字
// 返回值:
// true - 输入有效，并且数组中存在重复的数字
// false - 输入无效，或者数组中没有重复的数字
bool duplicate(int numbers[], int length, int* duplication)
{
}
首先，需要考虑边界条件、特殊输入（如 nullptr 指针、空字符串等）及错误处理。
题目给出的条件：
- 数组长度为
n。即数组长度不能为负，若长度为0，也没有结果，可知数组长度 n 应该为n > 0； - 数组里的所有数字都在
0 ~ n-1的范围内。即数组中的元素 e 应该(e >= 0) && (e <= n - 1)
// 考虑空指针以及数组长度是否合法
if (numbers == nullptr || length <= 0)
return false;
// 考虑数组中每个元素的值是否合法
for (int i = 0; i < length; i++)
{
if (numbers[i] < 0 || numbers[i] > length - 1)
return false;
}
解题思路及代码
《剑指Offer》中提供了三种解题思路，依次分析。
1. 数组排序
思路描述：
先把输入的数组进行排序，只需要遍历排序后的数组，判断相邻位置是否存在相同数字，如果存在，对 duplication 赋值返回，否则继续比较。
复杂度分析：
C++中的sort()函数是基于快速排序实现的，排序一个长度为n的数组需要O(nlogn)的时间。
时间复杂度：O(nlogn)
空间复杂度：O(1)
实现：
#include <cstdio>
#include <algorithm>
using namespace std;
// 参数:
// numbers: 一个整数数组
// length: 数组的长度
// duplication: (输出) 数组中的一个重复的数字
// 返回值:
// true - 输入有效，并且数组中存在重复的数字
// false - 输入无效，或者数组中没有重复的数字
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;
}
// 排序，sort()默认从小到大排序
sort(numbers, numbers + length);
// 注意 numbers[i + 1]，所以 i < length - 1，不要越界
for (int i = 0; i < length - 1; i++)
{
if (numbers[i] == numbers[i + 1])
{
*duplication = numbers[i];
return true;
}
}
return false;
}
2. 利用哈希表
题目中含有重复，第一时间想到哈希、set。这里我们用哈希来解。
思路描述：
- 扫描数组的每个元素，判断哈希表里是否已经包含该元素；
- 若哈希表中没有此元素，就加入哈希表，若已经存在该元素，则返回。
复杂度分析：
利用unordered_map，查询的时间复杂度为O(1)，算法的时间复杂度为O(n)，然鹅提高时间效率是以一个大小为O(n)的哈希表为代价的。
时间复杂度：O(n)
空间复杂度：O(n)
实现：
#include <cstdio>
#include <unordered_map>
using namespace std;
// 参数:
// numbers: 一个整数数组
// length: 数组的长度
// duplication: (输出) 数组中的一个重复的数字
// 返回值:
// true - 输入有效，并且数组中存在重复的数字
// false - 输入无效，或者数组中没有重复的数字
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;
}
unordered_map<int, int> hashmap;
for (int i = 0; i < length; i++)
{
if (hashmap.count(numbers[i]))
{
*duplication = numbers[i];
return true;
}
else
{
//hashmap.insert(unordered_map<int, int>::value_type(numbers[i], 1));
hashmap.insert({ numbers[i], 1 });
}
}
return false;
}
基于此，还有很多其他方法，例如：
- 开辟一个长度为 n 的
vector<bool>, 初始化为false； - 遍历数组，第一次遇到的数据，置为
true； - 再一次遇到已经置为
true的数据，说明是重复的，返回即可。
时间复杂度：O(n)
空间复杂度：O(n)
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;
}
vector<bool> f(length, false);
for (int i = 0; i < length; i++)
{
if (!f[numbers[i]])
{
f[numbers[i]] = true;
}
else
{
*duplication = numbers[i];
return true;
}
}
return false;
}
还有其他方法，就不细说了。
3. 重排数组
如题，由于数组的长度为n，数组中的数字都在0 ~ n-1范围内，于是，我们可知：
- 如果这个数组
没有重复的元素。那么一定是0 ~ n-1范围的每一个数都有了，此时将数组从小到大排列，一定是数字i出现在下标为i的位置。例如：有数组 arr 为 {3, 2, 4, 5, 0, 1}，该数组长度为6，没有重复数字，每个元素的值均在0 ~ 5范围内，重排之后为 {0, 1, 2, 3, 4, 5}，此时 arr[i] 的值为 i。 - 如果
有重复的元素。如果依旧假设下标为i的位置上的元素为数字i，那么就会发现有些位置可能有多个数字（即重复的数字），有些位置没有数字。
由此可知，我们只需要根据上述的内容想办法重排数组，让位置i的值为数字i，假设数组为 arr，步骤如下：
- 依次扫描数组，比较此时的
arr[i]跟i是否相等；若相等，说明位置跟数值匹配，继续扫描下一个元素； - 若不相等，将
值arr[i]与位置 arr[i] 上的值作比较，也就是说比较arr[i]与arr[arr[i]]，若相等，就找到了一个重复的数字； - 若不等，就互换，把
值arr[i]放到属于他的位置上。
时间复杂度：O(n)
空间复杂度：O(1)
#include <cstdio>
//#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
// 参数:
// numbers: 一个整数数组
// length: 数组的长度
// duplication: (输出) 数组中的一个重复的数字
// 返回值:
// true - 输入有效，并且数组中存在重复的数字
// false - 输入无效，或者数组中没有重复的数字
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。
知识点：数组
设函数为：
// 参数:
// numbers: 一个整数数组
// length: 数组的长度
// 返回值:
// 正数 - 输入有效，并且数组中存在重复的数字，返回值为重复的数字
// 负数 - 输入无效，或者数组中没有重复的数字
int getDuplication(const int* numbers, int length)
{
}
首先，依旧是需要考虑边界条件、特殊输入（如 nullptr 指针、空字符串等）及错误处理。
若数组长度为 n，则元素范围为 1 ~ n-1：
// 考虑空指针以及数组长度是否合法
if (numbers == nullptr || length <= 0)
return false;
// 考虑数组中每个元素的值是否合法
for (int i = 0; i < length; i++)
{
if (numbers[i] < 1 || numbers[i] > length - 1)
return false;
}
解题思路及代码
《剑指Offer》中提供了两种解题思路，依次分析。
1. 利用辅助数组
思路描述：
可以创建一个辅助数组，然后逐一把原数组的每个元素复制过去，并且原数组中的元素的值依旧是复制到该值对应的位置上去。
复杂度分析：
需要 O(n) 的辅助空间。
实现：
#include <iostream>
#include <vector>
using namespace std;
// 参数:
// numbers: 一个整数数组
// length: 数组的长度
// 返回值:
// 正数 - 输入有效，并且数组中存在重复的数字，返回值为重复的数字
// 负数 - 输入无效，或者数组中没有重复的数字
int getDuplication(const int* numbers, int length)
{
if (numbers == nullptr || length <= 0)
return -1;
for (int i = 0; i < length; i++)
{
if (numbers[i] < 0 || numbers[i] > length - 1)
return -1;
}
vector<int> arr(length);
for (int i = 0; i < length; i++)
{
if (numbers[i] == arr[numbers[i]])
return numbers[i];
arr[numbers[i]] = numbers[i];
}
return -1;
}
2. 二分查找思想
思路描述：
利用二分查找的思想，将 1~n 的数字从中间数字 m 分为 1~m 和 m+1 ~ n 两部分，然后统计两个范围内数字的个数，若 1~m 区间的数字个数超过 m，则一定包含重复的数字，否则 m+1 ~ n 一定包含重复的数字；然后继续将包含重复数字的区间一分为二，重复上过程，直到找到重复的数字。
复杂度分析：
由于利用了二分查找思想，若输入长度为 n 的数组，则统计次数的函数将被调用 O(logn) 次，每次需要 O(n) 的时间，则总时间复杂度为 O(nlogn)，空间复杂度为 O(1)。（与上面利用辅助数组的方法相比，相当于以时间换空间）
时间复杂度：O(nlogn)
空间复杂度：O(1)
注意：这种算法并不能保证找出所有重复的数字！！！
实现：
#include <iostream>
int countRange(const int* numbers, int length, int start, int end);
// 参数:
// numbers: 一个整数数组
// length: 数组的长度
// 返回值:
// 正数 - 输入有效，并且数组中存在重复的数字，返回值为重复的数字
// 负数 - 输入无效，或者数组中没有重复的数字
int getDuplication(const int* numbers, int length)
{
if (numbers == nullptr || length <= 0)
return -1;
for (int i = 0; i < length; i++)
{
if (numbers[i] < 0 || numbers[i] > length - 1)
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;
}
参考
《剑指Offer（第二版）》