每日leetcode第0023天 0041. First Missing Positive

这道题目的代码虽然不多,但确实是考查时间空间的利用的好题目。

要求中,时间复杂度是n,空间复杂度是1。

 

如果我们将元素直接进行双重循环遍历,

时间复杂度是n^2,空间复杂度是1。

 

如果我们将元素放到别的地方,例如哈希表中,再进行查询,

时间复杂度是n,空间复杂度是n。

 

如果我们将元素排序,再进行检查,

时间复杂度是nlogn,空间复杂度是1。

 

那么我们怎么做呢?

我们需要将原有数组中的数字进行交换,每个数字交换到它下标一致的位置上。

交换完后要记得再检查这个位置上换来的数字需不需要再交换,如果是负数,或者很大的数,又或者是重复的数(也就是那个位置上已经有一个好的了),那么就退出小循环。

从左往右都换好位置后,我们从下标1开始一个个检查,如果检查到某个位置上没有该数字就输出。最后如果检查完长度对应的数字了,就输出长度+1。

这个解法的时间复杂度是n,空间复杂度是1。复合要求。



关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录,贴了, 标签。将固定链接加入收藏夹。

每日leetcode第0023天 0041. First Missing Positive》有2条回应

  1. air说:

    你的代码好美

发表评论

您的电子邮箱地址不会被公开。