剑指offer 面试56题

面试56题：

题目：数组中数字出现的次数

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

解题思路：

方法一：异或运算，详见《剑指offer》P274

代码：

# -*- coding:utf-8 -*-

class Solution:

    # 返回[a,b] 其中ab是出现一次的两个数字

    def FindNumsAppearOnce(self, array):

        # write code here

        if len(array)<2:

            return

        resultEOR=0

        for i in array:

            resultEOR =resultEOR^ i

        index=self.FindFirstBit(resultEOR)

        res1,res2=0,0

        for j in array:

            if self.IsBit(j,index):

                res1^=j

            else:

                res2^=j

        return [res1, res2]

    def FindFirstBit(self,num):

        '''

        用于在整数num的二进制表示中找到最右边是1的位

        '''

        indexBit=0

        while(num&1==0 and indexBit<32):

            num=num>>1

            indexBit+=1

        return indexBit

    def IsBit(self,num,indexBit):

        '''

        用于判断在num的二进制表示中从右边起的indexBit位是否为1

        '''

        num = num >> indexBit

        return (num&1)

方法二：利用python自带的counter库

# -*- coding:utf-8 -*-

class Solution:

    # 返回[a,b] 其中ab是出现一次的两个数字

    def FindNumsAppearOnce(self, array):

        # write code here

        from collections import Counter

        res=Counter(array).most_common()[-2:]

        return list(map(lambda x:x[0],res))

巴特西

剑指offer 面试56题

最新文章

热门文章