学步园

<?php
    #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>";
?>

5
5
5
5