[leetcode]原地哈希/数组常见易混淆问题python

寻找重复数

对于该类问题，如果要求常量的额外空间，一般可考虑原地哈希，如果要求不修改数组，就要考虑别的方法了。

1-n，不修改数组，T287

题目：

给定一个包含n 1个整数的数组nums，数字都在**[1,n]范围内，假设只有一个**重复的整数，返回这个重复的数。

要求：

不修改nums，只用O(1)的额外空间。

求解：

如果包含重复数，则i→nums[i]是存在圈的，那么可以采用快慢指针的方法找到环的起点

def findDuplicates(nums):
    slow = nums[0]
    fast = nums[slow]
    while slow != fast:
        slow = nums[slow]
        fast = nums[nums[fast]]
    slow = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

1-n，可修改数组，T442

题目：

给定一个包含n个整数的数组nums，数字都在**[1,n]范围内，每个整数出现一次或两次，请你找出所有**出现两次的整数，并以数组形式返回。

要求：

时间复杂度O(n)，常量额外空间

def findDuplicates(nums):
    n = len(nums)
    if n <= 1:
        return []
    res = []
    #对下标为num-1的数取负，如果nums[num-1]已经是负数，那么num出现过
    for num in nums:
        num = abs(nums)
        if nums[num - 1] < 0:
            res.append(num)
        else:
        	nums[num - 1] = - nums[num - 1]
    return res

0-(n-1)，可修改数组，剑指offer03

题目：

给定一个包含n个整数的数组nums，数字都在**[0, n-1]**范围内，不知道有几个数字重复，也不知道重复几次，请找出任意一个重复的数字。

def findDuplicates(nums):
    n = len(nums)
    if n <= 1:
        return False
    #对数组中的每个数num，计算其本来的值num % n，如果处理前就>=n，说明下标为num是访问过的，如果没有访问过就 n
    for num in nums:
        num = num % n
        if nums[num] >= n:
            return num
        nums[num]  = n
    return False

寻找缺失数

所有缺失数，T448

题目：

给定一个包含n个整数的数组nums，数字都在[1, n]范围内，找出所有[1, n]范围内但不在nums中的数字，以数组形式返回结果。

def findDisappearedNums(nums):
    n = len(nums)
    res = []
    for num in nums:
        num = (num - 1) % n
        nums[num]  = n
    for i in range(n):
        if nums[i] <= n:
            res.append(i   1)
    return res

缺失的第一个正数，T41

题目：

给定一个未排序的整数数组nums，请找出其中没有出现的最小的正整数。

要求：

时间复杂度O(n)，空间复杂度O(1)

def findMissingOne(nums):
    n = len(nums)
    for i in range(n):
        if nums[i] <= 0:
            nums[i] = n   1
    for num in nums:
        num = abs(num)
        if num <= n:
            nums[num - 1] = - abs(nums[num - 1])
    for i in range(n):
        if nums[i] > 0:
            return i   1
    return n   1

这篇好文章是转载于：学新通技术网