1. 题目
在一个长度为n+1的数组里的所有数字都在 1~n 的范围内,所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字,但不能修改输入的数组。例如,如果输入长度为 8 的数组 {2,3,5,4,3,2,6,7},那么对应的输出是重复的数字 2 或者 3。
2. 思路
1-n的范围里面只有n个数字,由于数组中超过了n个数字,所以一定包含了重复的数字,所以某个范围中数字的个数很重要。
这道题目可以把 1~n 数字从中间的数字 m 分为两部分,前面一半为 1~m,后面一半为 m+1~n。如果 1~m 的数字的数目超过 m,那么这一半的区间里一定包含重复的数字;否则,另一半 m+1~n 的区间里一定包含重复的数字。
以长度为 8 的数组 {2,3,5,4,3,2,6,7} 为例分析查找的过程。长度为 8 所以中间的数字为 4,把这个数组分为两部分,一段是 1~4,另一部分是 5~7。接下来统计 1~4 这 4 个数字在数组中出现的次数,它们一共出现了 5 次,因此这 4 个数字中一定存在重复的数字。
接下来把 1~4 的范围一分为二,一段是 1、2 两个数字,另一段是 3、4 两个数字。数字 1、2 出现了两次,因此统计 3、4 出现的次数,它们一共出现了三次,因此存在重复的数字。再分别统计 3 和 4 出现的次数,最终输出的结果是 3。
#include <iostream> #include <vector> using namespace std; template <class T> class Duplication { public: int dup(const vector<T> &v); int get_count(const vector<T> v,int start,int end); }; template <class T> int Duplication<T>::dup(const vector<T> &v) { if(v.empty()||v.size()<=0) return -1; int start=1,end=v.size()-1; while(start<=end) { int middle=((end-start)>>1)+start; int count=get_count(v,start,middle);//第一次先找前半部分 if(start==end) if(count>1) return start; else break; if(count>middle-start+1)//如果前半部分的数字个数多于区间大小,则重复的前半部分肯定有重复的数字 end=middle; else start=middle+1;//重复的部分在后半部分 } return -2; } template <class T> int Duplication<T>::get_count(const vector<T> v,int start,int end) { if(v.empty()||v.size()<=0) return -1; int count=0; for(int i=0;i<v.size();++i) if(v.at(i)>=start&&v.at(i)<=end) ++count; return count; } int main() { vector<int> v; int n; cout<<" 请输入元素的个数."<<endl; cin>>n; for(int i=0;i<n;++i) { int t; cin>>t; v.push_back(t); } Duplication<int> d; cout<<d.dup(v)<<endl; return 0; }