• 算法学习——“原地哈希法”


    这个方法名是一名网友给起的,很形象。简单理解就是,在一个数组中,将数值为 a 的元素放到索引为 a 的位置上去,这是一种降低空间复杂度的方法,在一些有条件限制的场景中非常适用。下面给两个力扣的例子进行详解。

    练习题目1:

    LCR 120. 寻找文件副本

    设备中存有 n 个文件,文件 id 记于数组 documents。若文件 id 相同,则定义为该文件存在副本。请返回任一存在副本的文件 id

    示例 1:

    输入:documents = [2, 5, 3, 0, 5, 0]
    输出:0 或 5
    

    提示:

    • 0 ≤ documents[i] ≤ n-1
    • 2 <= n <= 100000

    这里利用的是 0 ≤ documents[i] ≤ n-1 这一点,所以我们可以把 documents[i] 的值放到 索引为 documents[i] 的位置,而 documents[i] 位置原来的值则放到索引 i 处,相当于这两个位置上的值进行交换。如果在交换的过程中发现,将要放进去的位置原来的值和即将放进去的值相等,则说明这个数出现了两次。

    1. class Solution(object):
    2. def findRepeatDocument(self, documents):
    3. # 先排序后匹配法:32ms, 21.1MB
    4. # documents = sorted(documents)
    5. # for i in range(len(documents) - 1):
    6. # if documents[i] == documents[i+1]:
    7. # return documents[i]
    8. # 哈希法:32ms, 22.3MB
    9. # num_set = set()
    10. # for i in range(len(documents)):
    11. # if documents[i] in num_set:
    12. # return documents[i]
    13. # else:
    14. # num_set.add(documents[i])
    15. # 原地哈希法:16ms, 19.8MB
    16. i = 0
    17. while i < len(documents):
    18. if documents[i] != i:
    19. if documents[documents[i]] == documents[i]:
    20. return documents[i]
    21. temp = documents[documents[i]]
    22. documents[documents[i]] = documents[i]
    23. documents[i] = temp
    24. else:
    25. i += 1

    练习题2:

    41. 缺失的第一个正数

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

    请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

    示例 1:

    输入:nums = [1,2,0]
    输出:3
    

    示例 2:

    输入:nums = [3,4,-1,1]
    输出:2
    

    示例 3:

    输入:nums = [7,8,9,11,12]
    输出:1
    

    提示:

    • 1 <= nums.length <= 5 * 10^5
    • -2^31 <= nums[i] <= 2^31 - 1

    这个是原地哈希 # 80ms, 20.4MB,空间占用少一些

    1. class Solution(object):
    2.   def firstMissingPositive(self, nums):
    3.       n = len(nums)
    4.       i = 0
    5.       while i < n:
    6.           if nums[i] > 0 and nums[i] <= n and nums[i] != i + 1:
    7.               if nums[nums[i] - 1] == nums[i]:
    8.                   nums[i] = -1
    9.                   i += 1
    10.               else:
    11.                   temp = nums[nums[i] - 1]
    12.                   nums[nums[i] - 1] = nums[i]
    13.                   nums[i] = temp
    14.           else:
    15.               i += 1
    16.       for i in range(0, n):
    17.           if nums[i] != i + 1:
    18.               return i + 1
    19.       return n + 1


    下面这个是先排序后查找,提交记录是:64ms, 21.1M,时间少一点

    1. class Solution(object):
    2.     def firstMissingPositive(self, nums):
    3.         n = len(nums)
    4.         nums = sorted(nums)
    5.         X = 1
    6.         for i in range(n):
    7.             if nums[i] == X:
    8.                 X += 1
    9.             elif nums[i] > X:
    10.                 break
    11.         return X

  • 相关阅读:
    ElasticSearch集群搭建及启动异常的问题
    源码安装部署drbd9
    Jetpack学习之Navigation(1)
    如何有效地管控人工智能的风险
    Python之爬虫
    刻字机尖角补偿
    分享一个基于微信小程序的高校图书馆预约座位小程序 图书馆占座小程序源码 lw 调试
    Redis之淘汰策略
    入门Rabbitmq
    【JavaWeb】关于JWT做认证授权的十万个理由(JSON Web Token)
  • 原文地址:https://blog.csdn.net/m0_37738114/article/details/133224837