笔者最近在找工作时，无意间读到了一本名为《剑指offer》的书，粗略翻阅了一下，感觉这将会是一本能让我不再苦恼于笔试和面试“手搓代码”的书。故笔者写下该系列博客记录自己的学习历程，希望能和这本书的读者朋友们一起交流学习心得。
介绍：《剑指Offer：名企面试官精讲典型编程题（第2版）》剖析了80个典型的编程面试题，系统整理基础知识、代码质量、解题思路、优化效率和综合能力这5个面试要点。
编程题链接：牛客网在线编程_算法面试_面试必刷TOP101 (nowcoder.com)
本博客关键词：不修改数组找出重复的数字
题设：
不修改数组找出重复的数字。
在一个长度为n+1的数组里所有的数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2,3,5,4,3,2,6,7}，那么对应的输出是重复的数字2或者3。
这道题和“数组中重复的数字”非常像，但是多加了一个限制：不能修改数组。
测试用例
- 符合要求的用例：
{1,2,3,4,5,5},{1,3,4,5,2,2,3} - 数字范围超过
n+1的用例：{1,7,8,9,7} - 输入为空：
{} - 没有重复数字：
{1,2,3,5,4}
解法一：哈希
这个解法不会修改输入的数组，时间复杂度是O(n)，空间复杂度也是O(n)。
int getDuplicate(vector<int> &nums)
{if (nums.size() <= 0){return -1;}for (auto num : nums){if (num >= nums.size()){return -1;}}// 通过unordered_set实现unordered_set<int> un_set;for (auto num : nums){if (un_set.find(num) != un_set.end()){return num;}un_set.insert(num);}return -1;
}
解法二：基于二分查找
这个方法是“用时间换空间”，时间复杂度为O(nlogn)，空间复杂度为O(1)
#include <iostream>
#include <unordered_set>
#include <vector>using namespace std;int getCount(vector<int> &nums, int start, int end)
{if (nums.size() <= 0){return 0;}int count = 0;for (auto num : nums){if (num >= start && num <= end){count++;}}return count;
}int getDuplicate(vector<int> &nums)
{if (nums.size() <= 0){return -1;}for (auto num : nums){if (num >= nums.size()){return -1;}}int start = 1;int end = nums.size() - 1;int middle = (start + end) / 2;int count;while (end >= start){count = getCount(nums, start, middle);if (count > middle - start + 1){end = middle;if (start == end){return start;}}else{start = middle + 1;if (start == end){return start;}}middle = (start + end) / 2;}return -1;
}int main(int argc, char const *argv[])
{vector<int> nums = {2, 2, 2, 2, 5, 5};// vector<int> nums = {1, 7, 8, 9, 7};// vector<int> nums = {};// vector<int> nums = {1, 2, 3, 5, 4};cout << getDuplicate(nums) << endl;return 0;
}
以上代码按照二分查找的思路来完成，如果输入数组长度为n，则函数getCount就要被调用O(logn)次，每次调用需要O(n)的时间，所以总的时间复杂度为O(nlogn)；由于没有使用辅助数组，该代码空间复杂度为O(n)。
这个方法的主要思路就是在数组长度为n+1，数组内数的范围是1~n的前提下，数组中肯定是有重复的元素的。二分法不是对数组本身进行二分法，而是对1~n这n个数进行二分法操作。
假如有数组{3,2,2,1,4,5}，这里一共有6个数，数组元素的范围在1~5之间，则中间元素就是3，先统计1~3在数组中出现的总次数，有4次，这说明肯定有一个数是重复的。这使基于1~3，在求中间元素就是2，统计1~2在数组中出现的次数，有3次，这说明在这个区间肯定有一个数是重复的。基于1~2，求中间元素值就是1，统计1在数组中出现的次数，只有1次，这时就可以说明重复的元素是2。
