保证原创，欢迎交流
如有雷同，纯属巧合

数组

P39

//
//  Created by Diane on 7/30/19.
//  Copyright © 2019 Diane. All rights reserved.
//

//  Given an array of length n, where each element falls in [0, n-1], You are asked to find a duplicate from this array
//

#include<iostream>
#include<assert.h>
using namespace std;
bool hasDupli(int *a, int n, int* dupli);

int main()
{
    // take input
    int n;
    while(true){
        try{
            scanf("%d", &n);
            if(n<0){
                throw "Length of array can not be less than 0, try again!\n";
            }
            break;
        }
        catch(const char* e){
            cout << e;
        }
    }
    int a[n];
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    // Check and print output
    int dupli;
    if(hasDupli(a, n, &dupli)){
        printf("Duplicate %d Found\n", dupli);
    }
    else{
        printf("No Duplicate\n");
    }
    return 0;
    
}

bool hasDupli(int a[], int n, int* p){
    if(n<0){
        return false;
    }
    int i = 0;
    while(i < n){
        if(a[i] == i){
            i++;
            continue;
        }
        else{
            if(a[a[i]] == a[i]){
                *p = a[i];
                return true;
            }
            else{
                int tmp = a[a[i]];
                a[a[i]] = a[i];
                a[i] = tmp;
            }
        }
    }
    return false;
}