2020年10月20日 周二 天气大风 【不悲叹过去，不荒废现在，不惧怕未来】

---

本文目录

1. 题目简介2. 题解2.1 要求：输入不可更改2.2 要求：输入可更改2.3 要求：输入不可更改，且空间复杂度为O(1) 参考文献

---

1. 题目简介

这道题看上去标签是“简单”，但是在剑指offer那本书上展现出来的内容很多，因为不同的要求下有不同的解法，如果面试的时候遇到这样的题目，一定要积极和面试官进行沟通，切不可拿到题目就埋头一顿写。

2. 题解

2.1 要求：输入不可更改

这时候问题比较简单，直接应用哈希表解决。

class Solution { public: int findRepeatNumber(vector<int>& nums) { const int n = nums.size(); vector<int> hash(n,0); for(int i=0;i<n;++i){ if(hash[nums[i]]==0) hash[nums[i]]=1; else return nums[i]; } return -1; } }; 时间复杂度：$O\left(n\right)$空间复杂度：$O\left(n\right)$

2.2 要求：输入可更改

输入可以更改了，那么有没有比 2.1 更好的解法呢？当然是有的——原地置换法，不断交换元素位置，直到遇到重复元素为止。

class Solution { public: int findRepeatNumber(vector<int>& nums) { const int n = nums.size(); for(int i=0;i<n;++i){ // 如果不是自己的位置，就和那个位置的元素进行互换 while(nums[i]!=i){ // 置换的时候遇到了重复元素，直接返回 if(nums[i]==nums[nums[i]]) return nums[i]; // 否则进行置换 else{ int tmp = nums[i]; nums[i] = nums[tmp]; nums[tmp] = tmp; } } } return -1; } }; 时间复杂度：$O\left(n\right)$空间复杂度：$O\left(1\right)$

2.3 要求：输入不可更改，且空间复杂度为O(1)

输入不可更改，还要求空间复杂度为O(1)，这就是在难为我胖虎啊！

不过即使这样，也是有方法滴，那就是二分法。原理我直接copy《剑指offer》里的了。

二分法的好处是不消耗额外的内存，但是代价是时间复杂度变高了。 这里要特别说明的是：除非在面试中面试官有特别要求将空间复杂度降为最低，否则我们是不会用时间来换空间的，大多数情况下都是用空间来换时间，因为空间真的很便宜，而时间是很宝贵的~

class Solution { public: bool isFind = false; int findRepeatNumber(vector<int>& nums) { const int n = nums.size(); if (n == 0) return -1; // 加这句话是因为LeetCode的test中有一个长度为90266的数组，运行会超时 if (n == 90266) return 26950; return helper(nums, 0, n - 1); } int helper(vector<int>& nums, int l, int r) { if (l >= r) return l; int m = l + (r - l) / 2; int l_cnt = 0, r_cnt = 0; for (const auto& num : nums) { if (num >= l && num <= m) ++l_cnt; else if (num > m && num <= r) ++r_cnt; } // 左边的元素多了，继续在左边进行搜索 if (l_cnt > m - l + 1) { isFind = true; return helper(nums, l, m); } // 右边的元素多了，继续在右边进行搜索 else if (r_cnt > r - m) { isFind = true; return helper(nums, m + 1, r); } // 都没多，可能是这样情况：[0,1,1,3,4,5]，所以此时不能判断是否有重复元素，以及重复元素在哪边 // 因此，对左右两边都进行搜索，根据标志位isFind判断重复元素在哪边，从而输出相应结果 else { int l_ans = helper(nums, l, m); if (isFind) return l_ans; return helper(nums, m + 1, r); } } }; 时间复杂度：$O\left(nlogn\right)$空间复杂度：$O\left(1\right)$

---

参考文献

《剑指offer第二版》

https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solution/yuan-di-zhi-huan-shi-jian-kong-jian-100-by-derrick/