位运算_在其他数都出现k次的数组中找到只出现一次的数

【题目】

　　给定一个整型数组arr和一个大于1的整数k，已知arr中只有一个数出现了一次，其他的数都出现了k次，请返回只出现1次的数。要求时间复杂度O(N)，空间复杂度O(1)。

【基本思路】

首先看一个七进制数无进位相加的问题。
七进制数a: 　　　　6 4 3 2 6 0 1
七进制数b:　　　　 3 4 5 0 1 1 1
无进制相加的结果:　2 1 1 2 0 1 2

可以看出，a和b无进位相加，在i位置上的结果就是 (a[i] + b[i]) % 7。
同理，k进制的两个数相加，i位置上的值为 (a[i] + b[i]) % k。那么，如果k个相同的k进制数相加，相加的结果一定是每一位上都为0。

首先设置一个变量filedArr，它是一个32位的k进制整数，且每个位置都是0，然后遍历arr，把遍历到的每一个整数都转换为k进制数，然后与filedArr进行无进位相加，遍历结束时，把32位的k进制整数rslt转换为10进制数，就是我们想要的结果。因为k个相同的k进制数无进位相加，结果一定是每个位都为0的k进制整数，所以只出现一次的那个数最终就会被剩下来。

【下面是使用PHP实现的代码】

<?php

//在其他数都出现k次的数组中找到只出现一次的数
class ExclusiveOr
{
    //获得只出现一次的数
    function produceUniqueNum($arr, $k)
    {
        $keys = range(0, 32);
        $filedArr = array_fill_keys($keys, 0);
        $fieldLength = count($filedArr);

        $arrlength = count($arr);
        for ($i = 0; $i < $arrlength; $i++) {
            $filedArr = $this->setExclusiveOr($filedArr, $arr[$i], $k);
        }

        //k进制的数转换成十进制的数
        return $this->getNumFromKSysNum($filedArr, $k);
    }

    //获得中间的步骤,获得只出现一次的k进制数
    function setExclusiveOr($filedArr, $value, $k)
    {
        $radixRslt = $this->getKSysNumFromNum($value, $k);

        $fieldLength = count($filedArr);
        for ($i = 0; $i < $fieldLength; $i++) {
            $filedArr[$i] = ($filedArr[$i] + $radixRslt[$i]) % $k;
        }  
        return $filedArr;
    }

    //将十进制的整数转换成k进制的数
    function getKSysNumFromNum($value, $k)
    {
        $index = 0;
        while ($value != 0) { 
            $rslt[$index++] = $value % $k;
            $value = $value / $k;
        }
        return $rslt;
    }

    //将k进制的数转换成的十进制的整数
    function getNumFromKSysNum($filedArr, $k)
    {
        $rslt = 0;
        $fieldLength = count($filedArr);

        for ($i = $fieldLength-1; $i >= 0; $i--) {
            $rslt = $rslt * $k + $filedArr[$i];
        }
        return $rslt;
    }

    function calc()
    {
        $k = 3; //k表示其他数出现的次数
        $arr = array(2, 2, 2, 9, 7, 7, 7, 3, 3, 3, 6, 6, 6);
    	print_r($this->produceUniqueNum($arr,$k));
    }
}

$obj = new ExclusiveOr(); 
$obj->calc();