配列に重複要素があるかどうかをどう判断するか

タイトル:
配列aにn個の要素があると仮定し、要素の取値範囲は1~nであり、配列に重複要素が存在するか否かをどのように判定するか.
考え方:
方法1:
隣接する要素が等しいかどうかを比較する配列ソート.
時間複雑度:O(nlogn)、空間複雑度:O(1)
方法2:
bitmap(ビットマップ)を使用して、長さN/8のchar配列を定義します.各bitは対応する数字が現れたかどうかを表します.配列を巡り、bitmapを使用して数字が現れたかどうかを統計します.
時間複雑度:O(n),空間複雑度:O(n)
方法3:
配列を巡り、i番目の位置の数字がjであると仮定すると、すべての数字が自分の対応する下表に現れるか、衝突するまで、jを交換することによってjを下のjと表記された位置に置き換える.
時間複雑度:O(n),空間複雑度:O(1)
コード:
方法1:

int cmp(const void* a,const void* b){
    return (*(int*)a-*(int*)b);
}

// sort and compare
bool findDuplicate(int* a,int n){
    if(a==NULL || n<=1)
        return false;

    qsort(a,n,sizeof(int),cmp);
    for(int i=0;ia[i])
            return true;
    }
    return false;
}

方法2:

// changed to the right position
bool findDuplicate_1(int* a,int n){
    if(a==NULL || n<=1)
        return false;
    
    for(int i=0;i