- 在一個長度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)。
- 數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個數(shù)字是重復(fù)的晦攒。
- 也不知道每個數(shù)字重復(fù)幾次。
- 請找出數(shù)組中任意一個重復(fù)的數(shù)字示弓。
- 例如损拢，如果輸入長度為7的數(shù)組{2,3,1,0,2,5,3}，那么對應(yīng)的輸出是第一個重復(fù)的數(shù)字2被碗。
解題思路
- 思路1: 對于數(shù)組先排序某宪，然后逐一比較即可
- 思路2: 劍指Offer 39頁
- 思路3: 建立哈希表，每次循環(huán)去map中查找蛮放，如果找不到則進入map缩抡，找到則返回這個重復(fù)數(shù)值
思路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) {
// 什么也不用干瞻想，開始下一個循環(huán)
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()){ // 找到了娩嚼，也就是以前出現(xiàn)過
*duplication = numbers[i];
return true;
}
else{ // 以前沒出現(xiàn)過蘑险，放入 map 中
mp[numbers[i]] = 1;
}
}
return false;
}
總結(jié)展望
- 思路一是自己思考出來的，比較大眾岳悟；思路二是看書自己實現(xiàn)的佃迄，效果應(yīng)該比思路一要好，但是看殴笊伲客上的運行時間和占用內(nèi)存呵俏，思路二甚至比思路一差，個人估計是數(shù)據(jù)量小的原因吧.
- 自己寫思路一的時候沒有考慮數(shù)組為空滔灶，數(shù)組長度小于0普碎，數(shù)組元素范圍沒在0-n 之間這些錯誤輸入的情況，導(dǎo)致程序不健壯录平，這一點以后要注意的.
