算法学习：找重复数字（分治法）

题目描述给定一个长度为n1n1n1的数组numsnumsnums数组中所有的数均在1∼n1∼n1∼n的范围内其中n≥1n≥1n≥1。请找出数组中任意一个重复的数但不能修改输入的数组。算法思路根据抽屉原理若数组长度为n1n1n1取值范围为nnn则至少存在一个重复数。本文采用二分法设定左右指针l,rl,rl,r用于标识查看的数值边界。Step1Step1Step1将数组按照数值大小划分为[1,n/2][1,n/2][1,n/2][n/21,n][n/21,n][n/21,n]Step2Step2Step2遍历原数组统计左部分数值范围的元素个数sssStep3Step3Step3计算sss与左部分数组长度的大小关系将指针范围挪到大于关系的部分更新左右指针算法过程classSolution{public:intduplicateInArray(vectorintnums){intres,l,r;intnnums.size()-1;l1;rn;// l从1开始intmid0;while(lr){mid(lr)1;intcount(0);for(autos:nums){countslsmid;}if(countmid-l1){rmid;}else{lmid1;}}returnr;}};