[剑指-40](php&python):数组中只出现一次的数字

说明：记录刷剑指offer，使用php与python两种语言，对解题思路以及涉及到的基本语法以及知识点做学习记录。其中对于每道题目进行粗略的分类。

题目来源

• 分类：数组
• 数组中出现一次的数字

题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。

解题思路

• 利用“异或”运算性质解题：任何一个数字异或它自己都等于0
  举例，对于数组中只有一个数字重复一次时，例如：{2, 6, 2}。利用异或运算：2的二进制为 0010，6的二进制为 0110 ，则2^6为0100 则 0100 与 0010 再异或计算得 0110 即为6；
  所以在数组中存在2个只出现的一次的数字，数组从头到尾一直异或，则异或的结果即为此2个数字的异或的结果（因为其他数字都出现了两次，在异或中全部抵消了）。2个数字不相同，所以异或的结果一定不为0，异或结果的二进制至少有一位为1，所以我们找寻异或结果第一个为1的位置即为n，则我们根据在第n个位置是否为1的这个标准把数组分为2个子数组，第一个子数组中每个数字的第n位都是1，而第二个子数组中每个数字的第n位都是0。之后两个子数组分别进行异或，得到两个值即为要求的数字（要求的两个数字一定分别存在两个数组中，因为两个数组第n为的是不同的）。

编程实现

PHP

<?php
运行时间：303ms

占用内存：2648k
    function FindNumsAppearOnce($array)
    {
        // write code here
        // return list, 比如[a,b]，其中ab是出现一次的两个数字
        if (empty($array) || count($array) < 2){
            return [];
        }
        
        $xor = 0;
        foreach($array as $arr){
            $xor ^= $arr;
        }
//      var_dump($xor);
        $bitLocation = FindOneLocation($xor);
//      var_dump($bitLocation);
        $num1 = 0;
        $num2 = 0;
        foreach($array as $arr){
            if(IsSameLocation($arr, $bitLocation)){
                $num1 ^= $arr;
            }else{
                $num2 ^= $arr;
            }
        }
        
        return array($num1, $num2);
        
    }
    function FindOneLocation($num){
        $bitCount = 0;
        while (($num & 1) == 0 && $bitCount <= 32){
            $bitCount++;
            $num = $num >> 1;
        }
        // var_dump($bitCount);
        return $bitCount;
    }
    function IsSameLocation($num, $location){
        $num = $num >> $location;
//      if(($num & 1) == 0){
//          return false;
//      } else {
//          return true;
//      }
        return ($num & 1);
    }
    
    var_dump(FindNumsAppearOnce(array(2,4,3,6,3,2,5,5)));
?>

Python

运行时间：26ms

占用内存：5728k
# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        if not array or len(array) <= 0:
            return []
        resOR = 0
        for arr in array:
            resOR ^= arr
#       print(bin(resOR).replace('0b',''))
        # 二进制从右向左 右为最地位 从0开始计数
        findOneLocation = self.FindLocationOne(resOR)
#       print(findOneLocation)
        num1, num2 = 0, 0
        for arr in array:
            if self.IsSameLocation(arr, findOneLocation):
                num1 ^= arr
            else:
                num2 ^= arr
        return num1, num2
        
    def FindLocationOne(self, num):
        bitCount = 0
        while num & 1 == 0 and bitCount <= 32:
            bitCount += 1
            num = num >> 1
        return bitCount
    def IsSameLocation(self, num, location):
        num = num >> location
        return num & 1
s = Solution()
print(s.FindNumsAppearOnce([2,4,3,6,3,2,5,5]))

知识点总结

1. python打印二进制数组
   比如bin(12345)回返回字符串'0b11000000111001' 这个时候在把0b去掉即可.
   print(bin(resOR).replace('0b',''))
2. 二进制从右向左计算位的， 右为最地位 从0开始计数