- 在一个长度为n的数组里的所有数字都在0到n-1的范围内。
- 数组中某些数字是重复的，但不知道有几个数字是重复的。
- 也不知道每个数字重复几次。
- 请找出数组中任意一个重复的数字。
- 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
解题思路
- 思路1: 对于数组先排序，然后逐一比较即可
- 思路2: 剑指Offer 39页
- 思路3: 建立哈希表，每次循环去map中查找，如果找不到则进入map，找到则返回这个重复数值
思路1代码，先排序，然后逐一比较即可
#include<iostream>
using namespace std;
class Solution {
public:
// 选择排序
bool duplicate(int numbers[], int length, int* duplication){
for(int i = 0; i < length - 1; ++i){
for(int j = i+1; j < length; ++j){
if(numbers[i]>numbers[j]){
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
}
}
for(int i = 0; i < length - 1; ++i){
if(numbers[i] == numbers[i+1]){
*duplication = numbers[i];
return true;
}
}
return false;
}
};
int main(){
Solution ss;
int a[] = {2, 1, 3, 1, 4};
int length = 5;
int dup = 0;
if(ss.duplicate(a, length, &dup)){
cout<<"Yes "<<dup<<endl;
}
else{
cout<<"No"<<endl;
}
}
class Solution {
public:
int core(int numbers[], int left, int right){
int pivot = numbers[left];
while(left < right){
while(left < right && numbers[right] >= pivot){
--right;
}
numbers[left] = numbers[right];
while(left < right && numbers[left] <= pivot){
++left;
}
numbers[right] = numbers[left];
}
numbers[left] = pivot;
return left;
}
void QuickSort(int numbers[], int left, int right){
if(left < right){
int pivot = core(numbers, left, right);
QuickSort(numbers, left, pivot-1);
QuickSort(numbers, pivot+1, right);
}
}
bool duplicate(int numbers[], int length, int* duplication) {
QuickSort(numbers, 0, length-1);
for(int i=0; i < length-1; ++i){
if(numbers[i] == numbers[i+1]){
*duplication = numbers[i];
return true;
}
}
return false;
}
};
class Solution {
public:
void swap(int numbers[], int i, int j){
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
void adjustHeap(int numbers[], int i, int length){
int temp = numbers[i];
for(int k=2*i+1; k < length; k = 2*k+1){
if(k+1 < length && numbers[k] < numbers[k+1]){
++k;
}
if(numbers[k] > temp){
swap(numbers, i, k);
i = k;
}
else{
break;
}
}
}
void heapSort(int numbers[], int length){
for(int i=length/2 - 1; i >= 0; --i){
adjustHeap(numbers, i, length);
}
for(int i=length-1; i > 0; --i){
swap(numbers, 0, i);
adjustHeap(numbers, 0, i);
}
}
bool duplicate(int numbers[], int length, int* duplication){
heapSort(numbers, length);
for(int i=0; i < length-1; ++i){
if(numbers[i] == numbers[i+1]){
*duplication = numbers[i];
return true;
}
}
return false;
}
};
思路2代码 剑指Offer 39页
#include<iostream>
using namespace std;
class Solution {
public:
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
bool duplicate(int numbers[], int length, int* duplication)
{
int i, j;
//增强程序的健壮性
if(numbers == NULL || length<=0){
return false;
}
for(i = 0; i < length; i ++){
if(numbers[i] < 0 || numbers[i] > length - 1){
return false;
}
}
for(i = 0; i < length; i ++) {
if(numbers[i] == i) {
// 什么也不用干，开始下一个循环
continue;
} else {
while (numbers[i] != i) {
if (numbers[i] == numbers[numbers[i]]) {
*duplication = numbers[i];
return true;
} else {
int temp = numbers[i];
numbers[i] = numbers[numbers[i]];
numbers[temp] = temp;
}
}
}
}
return false;
}
};
int main()
{
Solution ss;
//int a[] = {2, 1, 3, 1, 4};
//int length = 5;
int a[] = {2, 3, 1, 0, 2, 5, 3};
int length = 7;
int dup = 0;
if(ss.duplicate(a, length, &dup)){
cout<<"Yes "<<dup<<endl;
}
else{
cout<<"No"<<endl;
}
}
思路三，map
bool duplicate(int numbers[], int length, int* duplication) {
map<int, int> mp;
for(int i=0; i < length; ++i){
if(mp.find(numbers[i]) != mp.end()){ // 找到了，也就是以前出现过
*duplication = numbers[i];
return true;
}
else{ // 以前没出现过，放入 map 中
mp[numbers[i]] = 1;
}
}
return false;
}
总结展望
- 思路一是自己思考出来的，比较大众；思路二是看书自己实现的，效果应该比思路一要好，但是看牛客上的运行时间和占用内存，思路二甚至比思路一差，个人估计是数据量小的原因吧.
- 自己写思路一的时候没有考虑数组为空，数组长度小于0，数组元素范围没在0-n 之间这些错误输入的情况，导致程序不健壮，这一点以后要注意的.
