首页 > 代码库 > [剑指Offer] 50.数组中重复的数字
[剑指Offer] 50.数组中重复的数字
题目描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是重复的数字2或者3。
【思路1】需要一个容器来存储暂时没有重复的数字,在向后遍历的过程中如果在容器中找到相同数字则返回。
1 class Solution { 2 public: 3 // Parameters: 4 // numbers: an array of integers 5 // length: the length of array numbers 6 // duplication: (Output) the duplicated number in the array number 7 // Return value: true if the input is valid, and there are some duplications in the array number 8 // otherwise false 9 bool duplicate(int numbers[], int length, int* duplication) { 10 if(numbers == NULL) return false; 11 vector<int> vec; 12 int count = 0; 13 for(int i = 0;i < length;i ++){ 14 if(numbers[i] < 0 || numbers[i] > length - 1) return false; 15 if(find(vec.begin(),vec.end(),numbers[i]) != vec.end()){ 16 duplication[0] = numbers[i]; 17 return true; 18 }else{ 19 vec.push_back(numbers[i]); 20 } 21 } 22 if(duplication[0] == -1) return false; 23 else return true; 24 } 25 };
【思路2】不需要额外的数组来保存,题目里写了数组里数字的范围保证在0 ~ n-1 之间,所以可以利用现有数组设置标志,当一个数字被访问过后,可以设置对应位上的数 + n,之后再遇到相同的数时,会发现对应位上的数已经大于等于n了,那么直接返回这个数即可。
1 class Solution { 2 public: 3 // Parameters: 4 // numbers: an array of integers 5 // length: the length of array numbers 6 // duplication: (Output) the duplicated number in the array number 7 // Return value: true if the input is valid, and there are some duplications in the array number 8 // otherwise false 9 bool duplicate(int numbers[], int length, int* duplication) { 10 if(numbers == NULL) return false; 11 for(int i = 0;i < length;i ++){ 12 int index = numbers[i]; 13 if(index >= length){ 14 index -= length; 15 } 16 if(numbers[index] >= length){ 17 duplication[0] = index; 18 return true; 19 } 20 numbers[index] += length; 21 } 22 return false; 23 } 24 };
[剑指Offer] 50.数组中重复的数字
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。