/找到數組中任意一個重複的數字，或者所有重複元素 那如果是所有重複的呢？動態數組 數組長度n,數組中的元素在0~n-1之間 /

#include <iostream>
#include<vector>
#include<iterator>
#include<algorithm>
using namespace std;
//**********************方法一排序*******************************
//時間複雜度是O(nlgn)
int part(int a[],int low,int high){//划分成左右子数组，找到中间位置
 int temp=a[high];//最后一个元素作为中间元素
 int i=low-1;//i是慢速下标
 for(int j=low;j<high;j++){//挨个检查元素，比中间值小的在放在它的左边，大的放在右边
    if(a[j]<=temp){
        i++;
        swap(a[i],a[j]);
    }
 }
 swap(a[i+1],a[high]);
 return i+1;//找到第一个比中间值大的元素，返回它的位置,这就是中间元素所在位置
}
void QuickSort(int a[],int low, int high){
    if(low<high){
        int mid=part(a,low,high);
        QuickSort(a,low,mid-1);
        QuickSort(a,mid+1,high);
    }
}
void duplicate1(int *a,int length){
    bool flag=true;

    if(a==NULL || length<=0){
        flag=false;
        return ;
    }
    QuickSort(a,0,length-1);

    int i=0;
    int j=1;
    vector<int> findData;

    while(j<length){//畫個示意圖很容易理解 0 1 1 2 2 3 4 5

        while(a[i]!=a[j] && j<length){//注意這個j<length問題，最後一步如果沒有這個判斷，那麼i,j就會指向同一個值，就會出現重複壓入數組的情況
            i=j;
            j++;
        }
        if(a[i]==a[j]){
            findData.push_back(a[i]);
        }
        while(a[i]==a[j])
              j++;

    }
//這個實現找到任一個重複，vector數組找到所有重複數組
//    int findData=0;
//
//    for(int i=0;i<length-1;i++){
//        if(a[i]==a[i+1]){
//            findData=a[i];
//            break;
//        }
//    }

    for(vector<int>::const_iterator it = findData.begin(); it !=findData.end(); ++it)
        cout<<*it<<" ";

    cout<<endl;
}
//*********************方法二哈希表******************************
//時間複雜度是O(n),需要額外的空間O(n)
void duplicate2(int *a, int length){

    int hashtable[length]={0};
    for(int i=0;i<length;i++){
            hashtable[a[i]]++;
    }
    vector<int> findData;
    for(int i=0;i<length;i++){
        if(hashtable[a[i]]>1)//需要去重
        {
            findData.push_back(a[i]);
        }

    }
    //重複過程
    vector<int>::iterator iter=findData.begin();
    iter=unique(findData.begin(),findData.end());//只能刪除相鄰的重複元素
    findData.erase(iter,findData.end());

    for(vector<int>::const_iterator it = findData.begin(); it !=findData.end(); ++it)
        cout<<*it<<" ";

    cout<<endl;


}
//**********************方法三交換*******************************
/*
O(n)時間找到數組中重複的數字，並且不需要額外分配空間，空間複雜度為O(1)
*/
//如果下標i與在所在的數值不一致，那就交換以數值為下標的數值，前提是這兩個數值不一致，如果不同的下標同一個數字，那就說明找到重複的。
void duplicate3(int *a,int length){
    bool flag=false;
    if(a==NULL ||length<=0){
        return ;
    }
    for(int i=0;i<length;i++){
        if(a[i]<0 || a[i]>length-1)
            return ;
    }

    vector<int> findData;
    for(int i=0;i<length;i++){
        while(a[i]!=i){
            if(a[i]==a[a[i]]){
                    vector<int>::iterator it=find(findData.begin(),findData.end(),a[i]);
                    if(it!=findData.end())//數組中沒有這個元素再放進去，有的話進行下一輪判斷
                        break;
                    findData.push_back(a[i]);
                    flag=true;
                    break;
            }
            //否則就交換以這個數值為下標的數字
            else{
                int temp=a[i];
                a[i]=a[temp];
                a[temp]=temp;
            }
        }
    }


    for(vector<int>::const_iterator it = findData.begin(); it !=findData.end(); ++it)
        cout<<*it<<" ";

    cout<<endl;
}
int main()
{
    int a[]={0,0,1,2,2,3,4,4,5,6};
   // duplicate1(a,8);
   //duplicate2(a,10);

    duplicate3(a,10);

    return 0;
}