Python教程

Python 剑指offer 03

本文主要是介绍Python 剑指offer 03,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

在这里插入图片描述
最容易想到的办法是双遍历,但实际不可行,消耗的内存和运行的时间都会很大
解法1
用字典统计数字出现的次数,如果数字已经在字典里则返回数字

# 解法1
class Solution1:
    def findRepeatNumber(self, nums) -> int:
        count = dict()
        for num in nums:
            if num not in count:
                count[num] = 1
            else:
                return num

解法2
原地哈希法,让每一个数字出现在固定的位置,如果当前数字在归位时发现位置已经被占了那么该数字就是要找的数字

# 解法2
class Solution2:
    def findRepeatNumber(self, nums) -> int:
        n = len(nums)
        for i in range(n):
            while i != nums[i]:
                if nums[i] == nums[nums[i]]:
                    return nums[i]
                temp = nums[i]
                nums[i], nums[temp] = nums[temp], nums[i]
这篇关于Python 剑指offer 03的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!