绑定完请刷新页面
取消
刷新

分享好友

×
取消 复制
LeetCode41, 一道题让你明白 in-place是什么?又怎么设计in-place算法?
2020-03-19 16:25:42

今天是LeetCode题解系列第21篇,今天来看一道人狠话不多的题目。
今天的题目题面非常简单,只有一句话,给定一个整数数组,要求返回小的不在数组当中的正整数。
看起来有些拗口,简单解释一下。我们都知道正整数就是从1开始的整数,所以这道题就是从1开始找到个不在数组当中的元素。我们来看下样例:
样例 1:
Input: [1,2,0]
Output: 3
样例 2:
Input: [3,4,-1,1]
Output: 2
样例 3:
Input: [7,8,9,11,12]
Output: 1
注意:
算法必须是,并且只能使用的存储。

分析


在后面的要求出来之前,我们可能觉得这道题也不是那么难,很容易就想到解法,但是有了这两条限制之后就没那么简单了。我们遍历数组就需要的复杂度了,怎么还能找出小未出现的元素呢?而且还不能申请额外的数组,只能用常数级的存储,显然各种辅助数组和容器是不能用了。
我们直接这么苦苦思索是很难想出解法的,不如来循序渐进。
我们先来假设没有这些限制条件的话应该用什么方法,容易想到的应该是排序。我们将数组排序,一旦数组有序了之后就方便了。我们从小到大遍历,很容易就确定哪些元素出现过哪些元素没有。那么想要找出来不在数组当中的小自然数自然也是轻而易举。分析一下排序我们可以发现,在此过程当中我们并没有用到额外的空间,不满足条件的只有我们的时间复杂度是而不是
我们写下代码:
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
nums = sorted(nums)
if len(nums) == or nums[] > 1:
return 1

mark = 1
for i in nums:
if i == mark:
mark += 1

return mark
那我们反过来,如果保证空间可以随意使用,但是对时间复杂度进行限制,我们能想到什么办法呢?
应该也很容易想出来,就是引入额外的容器。比如hashset。hashset的增删改查的复杂度都可以近似看成是常数级。我们只需要遍历一次数组,将所有元素插入hashset当中,同时记录下元素的大小值,后遍历一下小值和大值这个区间,找出不在hashset当中小的元素即可。n个元素的数组我们可以很容易证明,我们一定可以在n次查找以内找到不在数组当中的自然数。
这段代码也不难写:
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
st = set()
if len(nums) == :
return 1

mini, maxi = 3e9, -3e9

# 插入set当中维护
for i in nums:
st.add(i)
mini = min(mini, i)
maxi = max(maxi, i)

# 从1开始找到个不在set当中的元素
# 由于nums只有n个元素,我们可以可以在n次遍历当中找到
for i in range(1, maxi):
if i not in st:
return i

# 如果从1到maxi都存在,那么就放回maxi+1和1的大值
# 因为如果maxi小于1,那么上面的循环不会执行,所以要和1取大值
return max(maxi+1, 1)
上面的两种做法一种进行了高复杂度的排序,另一种则用到了额外的存储。看起来这是一个两难问题,我们不想排序就需要用到存储,如果不想用存储呢,那么则需要元素有序。我们仔细分析一下这两种情况,就可以找到问题的症结了,我们有没有什么办法可以两全其美,既不用额外的存储又可以保证元素的有序呢?如果我们可以找到一种方法,那么这个问题就解决了。
这也是我们解题的时候的一个常规的套路,就是对于一些题目而言有一些算法是比较明显的,但是可能因为这样或那样的限制使得并不能应用在当前的问题当中。但是没关系,我们一样可以往这方面去想,先找到一个不那么合适的解法,在此基础上谋求突破,很多时候要比凭空想出一个完美的方法来容易许多。
那么我们怎么突破呢?
还要从题目的要求入手,题目当中规定只能使用常数的存储空间,意味着我们不能额外开辟数组或者其他容器来存储数据。有经验的同学可能已经反映过来了,这是in-place的套路
in-place并不是一个算法,而是一种思想。它出现的原因也非常简单,因为我们申请数组等容器的时候需要通过操作系统向内存申请空间,这是需要消耗内存和时间的。所以在一些高性能的场景下,我们会希望尽量避免空间申请操作。比如我们想要对数组进行排序,我们可以拷贝数组,对拷贝出的数组排序之后返回。也就是说我们return了一个新的数组,只是其中的元素和原来一模一样。如果是in-place的方法,我们则不会另外创建数组,而在原数组上进行修改。
这个思想在机器学习当中大量用到,比如Python的numpy和pandas等库当中默认不是in-place的,这样方便数据的追踪,并且进行的改动不会覆盖原数据,如果一次尝试不对还可以多次尝试。而如果我们需要保证性能,我们则需要设置参数,来执行一个in-place的操作。
这题其实已经暗示得很明显了,我们需要存储数据,但是又不让我们申请空间,于是我们只有in-place一条路可以走了。
我们需要设计一个in-place的算法,让我们可以判断元素的存在性。再加上题目中的限制是正整数,而且我们要找的是个没有出现的正整数。如果数组的长度是n,那么其实我们可以锁定,答案一定在[1, n+1]之间。如果我们能把这个区间写出来,其实解法已经就在我们眼前了。
既然答案在区间[1, n+1]中间,我们又需要设计一个in-place的方法,那么我们可以很正常地想到,我们可以将数字放到对应的下标当中去。1放到下标1当中,0放到0当中。
比如[3, 1, 0, 5],我们拿到个元素是3,我们把它放到它应该在的位置,也就是5的位置下去,这个时候我们再来放5,由于5超过了数组的长度,所以进行丢弃。我们往下重复如上的过程,到后的时候,我们得到的数据情况如下:[0, 1, 5, 3],我们遍历一下数组,发现和下标不匹配的位置就是5,它应该对应的数据是2,所以2就是答案。
我乍看到这种算法的时候还是很惊艳的,后来想到了in-place之后,又觉得非常巧妙, 没想到利用in-place的思想还能出出这么巧妙的题。同样,如果你事先就了解过in-place的相关处理,一定也可以对这个算法理解得更加透彻。后,我们来看代码:
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
# 因为是正整数,所以数组长度需要扩大1
nums.append()

for i in range(n):
if i == nums[i]:
continue

while True:
# 不停地交换元素,直到范围超界或者是已经放好了为止
# 需要考虑nums[i] 和 nums[nums[i]]相等的情况,这时候也不应该交换
val = nums[i]
if val > n or val < or val == i or val == nums[val]:
break
nums[i], nums[val] = nums[val], val


for i in range(1, n+1):
if i != nums[i]:
return i

return n+1
后,我们来分析一下这个算法的复杂度,为什么我们在一重循环当中还套了一个while循环,但是它仍然是的算法呢?
这个问题我们之前在介绍two pointers和尺取法的时候就曾经介绍过,我们在分析复杂度的时候不能只简单地看有几重循环,我们需要细致地分析。我们要忽略循环,回到问题的本质。我们用循环的本质是为了能够让每个元素放到对应的位置,一共需要安排的元素数量是固定的是n个,位置也是固定的是n个,一个元素只有一个位置。那么我们一次交换至少可以让一个元素放到正确的位置,那么问题来了,我们想要把所有元素放置好,需要循环多少次?
我这样问,大家应该很清楚,一次少放一个,一共n个,显然多放n次。那我们再看while循环当中,每执行一次,不就是放好了一个元素吗?外围的循环只是用来枚举元素的,并不会引入额外的计算,所以这当然是一个的算法。
后,今天的题目官方标的难度是Hard,题目本身不难,由于加上了很多限制才提升了难度。题目本身并没有用到新的算法,纯粹是对思维和逻辑的考验。也因此,我觉得它是一道非常纯粹的题,纯粹在于它并用不到新的算法,也用不到新的数据结构,就是考察我们分析问题和思考问题的能力。而许多问题则针对性很强,如果之前没有学过对应的算法则无法做得出来,所以从这点上来说这题更加公平,非常适合面试。我已经进行了预约,以后如果有面试机会,我可能会问候选人这个问题。
今天的文章就是这些,如果觉得有所收获,请顺手点个在看或者转发吧,你们的举手之劳对我来说很重要。



分享好友

分享这个小栈给你的朋友们,一起进步吧。

TechFlow
创建时间:2020-03-19 11:13:43
机器学习、算法与数据结构、大数据相关和Python。 从纯基础开始的算法领域入门以及进阶内容。
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅:虚拟交易,一经交易不退款;若特殊情况,可3日内客服咨询

• 专区发布评论属默认订阅所评论专区(除付费小栈外)

栈主、嘉宾

查看更多
  • chengycz
    栈主

小栈成员

查看更多
  • 兔子爱喝红茶
  • 小雨滴
  • ittttliu
  • 栈栈
戳我,来吐槽~