【数组】数组中重复的数字【剑指offer】

/*
思路1：先排序，依次遍历找出重复的数。O(nlogn) O(1)
思路2：哈希表，从头到尾扫描数组，如果哈希表中没有该数字，把它加入哈希表；如果存在，找到一个。O(n) O(n) 
思路3：交换法，从头到尾扫描数组，当扫描到下标为i的数字时，首先比较这个数字是不是等于i，
        如果是接着扫描下一个数字；如果不是，就拿它和第m个数字进行比较，如果它和第m个数字相等，就找到了一个重复的数字（该数字在下标为i和下表为m的位置都出现过）。
        O(n) O(1)
*/

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <map>
using namespace std;


class Solution1{
public:
    // Parameters:
    //        numbers:     an array of integers
    //        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) 
    {
        //合法性检验
        if(numbers == NULL || length <=0)
            return false;
        for(int i=0;i<length;i++)
        {
            if(numbers[i]<0 || numbers[i]>length-1)
                return false;
        }
        //借助vector排序
        vector<int> v;
        for(int i=0;i<length;i++)
            v.push_back(numbers[i]);
        sort(v.begin(), v.end());
        //copy(v.begin(), v.end(), ostream_iterator<int>(cout," "));  //打印排序后的结果
        // cout<<endl;

        int flag = v[0];
        for(int i=1;i<length;i++)
        {   
            if(flag == v[i])
            {
                // duplication = new int(flag);
                // cout<<*duplication<<endl;

                *duplication = flag;
                return true;
            }
            else
                flag = v[i];
        }
        return false;
    }

};


class Solution2{
public:
    // Parameters:
    //        numbers:     an array of integers
    //        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) 
    {
        //合法性检验
        if(numbers == NULL || length <=0)
            return false;
        for(int i=0;i<length;i++)
        {
            if(numbers[i]<0 || numbers[i]>length-1)
                return false;
        }

        map<int, int> hash; 
        for(int i=0;i<length;i++)
        {
            hash[numbers[i]]++;
            //当m数字存在在哈希表中,则重复
            if(hash[numbers[i]] >1 )
            {
                *duplication = numbers[i];
                return true;
            }
        }
        return false;
    }
};


class Solution3{
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) 
    {
        //合法性检验
        if(numbers == NULL || length <=0)
            return false;
        for(int i=0;i<length;i++)
        {
            if(numbers[i]<0 || numbers[i]>length-1)
                return false;
        }

        //遍历数组
        for(int i=0;i<length;i++)
        {
            //2, 3, 1, 0, 2, 5, 3
            //1, 2, 3, 4, 5, 6, 7
            //如果i对应位置的数字与i不相等
            while(numbers[i] != i)
            {
                int m = numbers[i];
                if(numbers[i] == numbers[m])
                {
                    *duplication = m;
                    return true;
                }

                //交换两个数字
                int temp = numbers[i];
                numbers[i] = numbers[temp];
                numbers[temp] = temp;
            }
        }
        return false;
    }
};


int main()
{

    int num[] = {0,2,5,1,3,2,1};
    int a[] = {-1};

    //排序法
    // Solution1 solu1;
    // bool x = solu1.duplicate(num, 7, a);
    // cout<<"isDupLication: "<<x<<endl;
    // if(x == true)
    //     cout<<"first num: "<<*a<<endl;


    //哈希表
    // Solution1 solu2;
    // bool x = solu2.duplicate(num, 7, a);
    // cout<<"isDupLication: "<<x<<endl;
    // if(x == true)
    //     cout<<"first num: "<<*a<<endl;


    //索引
    Solution3 solu3;
    bool x = solu3.duplicate(num, 7, a);
    cout<<"isDupLication: "<<x<<endl;
    if(x == true)
        cout<<"first num: "<<*a<<endl;



    return 0;
}