#a[n+1]共有n+1个数，数值范围是1~n，a中有1个数重复，其他各不相同，找出这个相同的数

#第一种方法，利用 a数组的和减去1+2+3+...+n的和，得到的结果就是重复数字
function get_dup($a) {
    $size = count($a);
    $suma = 0;
    $sumn = 0;
    for ($i = 0; $i < $size; $i++) {
        $suma += $a[$i];
        $sumn += $i;
    }

    return $suma - $sumn;
}

#第二种方法，利用异或
#异或的性质: A xor A = 0; 0 xor A = A;
#解析：假设重复的数是A，除了A以外的1~n的异或值为B，则对数组a所有数进行异或，可以得到 A xor A xor B = B
#对于1~n的各不相同的n个数，对他们进行异或的值是 A xor B
#对上述两步得到的值进行异或有 (A xor A xor B) xor (A xor B) = A，这样就求出了A
function get_dup_xor($a) {
    $x = $a[0];
    for ($i = 1; $i < count($a); $i++) {
        $x ^= $a[$i] ^ $i;
    }

    return $x;
}

#第三种方法，使用bitmap
function get_dup_bitmap($a) {
    $bitmap = array();
    for ($i = 0; $i < count($a); $i++) {
        if (!isset($bitmap[$a[$i]])) {
            $bitmap[$a[$i]] = 1;
        } else {
            return $a[$i];
        }
    }
}

#第四种方法，利用修改数组内值
#这种方法在数组以0开头的时候会有问题，因为a[0]=0,下次还是跳到a[0] = null,直接就把0当重复的输出了
#当然了，按照题意不可能以0开头
function get_dup_mod($a) {
    $i = 0;
    while ($i < count($a)) {
        if ($a[$i] == null) {
            return $i;
        }
        $j = $i;
        $i = $a[$i]; #如果数组中存在重复值，则$i必然会两次指向同一个下标，第二次指向同一个元素时元素已置为null
        $a[$j] = null;
    }
}

$a = array(1, 2, 5, 3, 4, 5, 6, 7, 8, 9);
echo get_dup($a) . "<br>";
echo get_dup_xor($a) . "<br>";
echo get_dup_bitmap($a) . "<br>";
echo get_dup_mod($a) . "<br>";

参考来源：https://www.cnblogs.com/zemliu/archive/2012/09/30/2709012.html