剑指offer学习笔记:03数组中的重复数字

题目

剑指offer学习笔记:03数组中的重复数字

解法1:

使用哈希表或者set,时间复杂度O(n),空间复杂度O(n)

哈希表(字典)

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
    	temp_dict = {}
    	for inum in nums:
    		if inum not in temp_dict:
    			temp_dict[inum] = 1
    		else:
    			return inum

剑指offer学习笔记:03数组中的重复数字
思路:新建一个字典,利用字典key值唯一的特点,如果key值不在(字典的in操作判断的是key值),则添加新的键值对,这里的值就无所谓是多少了,如果字典中已经存在这个key值,则说明是重复元素,返回

set集合

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
    	temp_dict = set()
    	for inum in nums:
    		if inum not in temp_dict:
    			temp_dict.add(inum)
    		else:
    			return inum

与使用字典基本一致,运行时间也几乎一样,利用的也是set的不重复性
当然对于set来说,可以不适用in操作判断,通过add后的set长度来判断也可以:

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        data_set = set()
        for i in range(len(nums)):
            data_set.add(nums[i])
            if len(data_set) < i+1: #添加后小于说明没有添加成功,即为重复元素
                return nums[i]

为何不使用list

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
    	temp_list = []
    	for inum in nums:
    		if inum not in temp_list:
    			temp_dict[inum] = 1
    		else:
    			return inum

来看一下这样运行的时间:
剑指offer学习笔记:03数组中的重复数字
可以看到虽然通过了,但是运行时间相对与前面两个方法很慢,原因在于in操作的差别
list的in操作时间复杂度为O(n),可以理解为内部是通过遍历去寻找是否存在
而set和dict的in操作时间复杂度为O(1)

参考:Python-list 和 dict 内置操作的时间复杂度.

因此加上层遍历原数组,使用list的时间复杂度为O(n2)

原地哈希

如果对数组进行原地操作,则空间复杂度为O(1)。上面的方法并没有利用到题目中的条件“所有数字都在 0~n-1 的范围内”,所以针对这个条件可以使用原地哈希进行优化

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            while nums[i] != i:
                curr_value = nums[i]
                if nums[curr_value] != curr_value:
                    nums[curr_value],nums[i] = nums[i],nums[curr_value]
                else:
                    return curr_value

题解:原地置换

上一篇:大数据概述


下一篇:大数据概述