LeetCode 41,一题解读in-place思想

2019/04/10 10:10
阅读数 34

本文始发于个人公众号:TechFlow,原创不易,求个关注

<br>

<section id="nice" data-tool="mdnice编辑器" data-website="https://www.mdnice.com" style="font-size: 16px; color: black; padding: 10px; line-height: 1.6; word-spacing: 0px; letter-spacing: 0px; word-break: break-word; word-wrap: break-word; text-align: left; font-family: Optima-Regular, Optima, PingFangSC-light, PingFangTC-light, 'PingFang SC', Cambria, Cochin, Georgia, Times, 'Times New Roman', serif;"><p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">今天是<strong style="font-weight: bold; color: rgb(71, 193, 168);">LeetCode题解系列第21篇</strong>,今天来看一道人狠话不多的题目。</p> <h2 data-tool="mdnice编辑器" style="font-weight: bold; font-size: 24px; border-bottom: 2px solid rgb(89,89,89); margin-bottom: 50px; margin-top: 100px; color: rgb(89,89,89);"><span style="font-size: 22px; display: inline-block; border-bottom: 2px solid rgb(89,89,89);">题面</span></h2> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">题目非常简单,只有一句话,给定一个整数数组,要求返回最小的不在数组当中的正整数。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">看起来有些拗口,简单解释一下。我们都知道正整数就是从1开始的整数,所以这道题就是从1开始找到第一个不在数组当中的元素。我们来看下样例:</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;"><strong style="font-weight: bold; color: rgb(71, 193, 168);">样例 1:</strong></p> <pre data-tool="mdnice编辑器" style="margin-top: 10px; margin-bottom: 10px;"><code style="display: block; font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; border-radius: 0px; font-size: 12px; -webkit-overflow-scrolling: touch;">Input: [1,2,0] Output: 3 </code></pre> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;"><strong style="font-weight: bold; color: rgb(71, 193, 168);">样例 2:</strong></p> <pre data-tool="mdnice编辑器" style="margin-top: 10px; margin-bottom: 10px;"><code style="display: block; font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; border-radius: 0px; font-size: 12px; -webkit-overflow-scrolling: touch;">Input: [3,4,-1,1] Output: 2 </code></pre> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;"><strong style="font-weight: bold; color: rgb(71, 193, 168);">样例 3:</strong></p> <pre data-tool="mdnice编辑器" style="margin-top: 10px; margin-bottom: 10px;"><code style="display: block; font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; border-radius: 0px; font-size: 12px; -webkit-overflow-scrolling: touch;">Input: [7,8,9,11,12] Output: 1 </code></pre> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;"><strong style="font-weight: bold; color: rgb(71, 193, 168);">注意:</strong></p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">算法的<strong style="font-weight: bold; color: rgb(71, 193, 168);">时间复杂度</strong>必须是<span><img style="margin: 0 auto; width: auto; max-width: 100%; display: inline;" class="equation" src="https://juejin.im/equation?tex=O(n)" alt></span>,并且只能使用<span><img style="margin: 0 auto; width: auto; max-width: 100%; display: inline;" class="equation" src="https://juejin.im/equation?tex=O(1)" alt></span>的存储空间。</p> <h2 data-tool="mdnice编辑器" style="font-weight: bold; font-size: 24px; border-bottom: 2px solid rgb(89,89,89); margin-bottom: 50px; margin-top: 100px; color: rgb(89,89,89);"><span style="font-size: 22px; display: inline-block; border-bottom: 2px solid rgb(89,89,89);">分析</span></h2> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">在注意出来之前,我们可能觉得这道题也不是那么难,很容易就想到解法,但是有了这两条限制之后就没那么简单了。我们遍历数组就需要<span><img style="margin: 0 auto; width: auto; max-width: 100%; display: inline;" class="equation" src="https://juejin.im/equation?tex=O(n)" alt></span>的复杂度了,怎么还能找出最小未出现的元素呢?而且还不能申请额外的数组,只能用常数级的存储,显然各种辅助数组和容器是不能用了。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">我们直接这么苦苦思索是很难想出解法的,不如来<strong style="font-weight: bold; color: rgb(71, 193, 168);">循序渐进</strong>。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">我们先来假设没有这些限制条件的话应该用什么方法,最容易想到的应该是<strong style="font-weight: bold; color: rgb(71, 193, 168);">排序</strong>。我们将数组排序,一旦数组有序了之后就方便了。我们从小到大遍历,很容易就确定哪些元素出现过哪些元素没有。那么想要找出来不在数组当中的最小自然数自然也是轻而易举。分析一下排序我们可以发现,在此过程当中我们并没有用到额外的空间,唯一不满足条件的只有我们的时间复杂度是<span><img style="margin: 0 auto; width: auto; max-width: 100%; display: inline;" class="equation" src="https://juejin.im/equation?tex=O(nlogn)" alt></span>而不是<span><img style="margin: 0 auto; width: auto; max-width: 100%; display: inline;" class="equation" src="https://juejin.im/equation?tex=O(n)" alt></span>。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">我们写下代码:</p> <pre class="custom" data-tool="mdnice编辑器" style="margin-top: 10px; margin-bottom: 10px;"><code class="hljs" style="overflow-x: auto; padding: 16px; color: #383a42; background: #fafafa; display: -webkit-box; font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; border-radius: 0px; font-size: 12px; -webkit-overflow-scrolling: touch;"><span class="hljs-class" style="line-height: 26px;"><span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">class</span> <span class="hljs-title" style="color: #c18401; line-height: 26px;">Solution</span>:</span><br> <span class="hljs-function" style="line-height: 26px;"><span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">def</span> <span class="hljs-title" style="color: #4078f2; line-height: 26px;">firstMissingPositive</span><span class="hljs-params" style="line-height: 26px;">(self, nums: List[int])</span> -&gt; int:</span><br> nums = sorted(nums)<br> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">if</span> len(nums) == <span class="hljs-number" style="color: #986801; line-height: 26px;">0</span> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">or</span> nums[<span class="hljs-number" style="color: #986801; line-height: 26px;">0</span>] &gt; <span class="hljs-number" style="color: #986801; line-height: 26px;">1</span>:<br> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">return</span> <span class="hljs-number" style="color: #986801; line-height: 26px;">1</span><br> <br> mark = <span class="hljs-number" style="color: #986801; line-height: 26px;">1</span><br> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">for</span> i <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">in</span> nums:<br> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">if</span> i == mark:<br> mark += <span class="hljs-number" style="color: #986801; line-height: 26px;">1</span><br> <br> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">return</span> mark<br></code></pre> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">那我们反过来,如果保证空间可以随意使用,但是对时间复杂度进行限制,我们能想到什么办法呢?</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">应该也很容易想出来,就是引入额外的容器。比如hashset。hashset的增删改查的复杂度都可以近似看成是常数级。我们只需要遍历一次数组,将所有元素插入hashset当中,同时记录下元素的最大最小值,最后遍历一下最小值和最大值这个区间,找出不在hashset当中最小的元素即可。n个元素的数组我们可以很容易证明,我们一定可以在n次查找以内找到不在数组当中的自然数。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">这段代码也不难写:</p> <pre class="custom" data-tool="mdnice编辑器" style="margin-top: 10px; margin-bottom: 10px;"><code class="hljs" style="overflow-x: auto; padding: 16px; color: #383a42; background: #fafafa; display: -webkit-box; font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; border-radius: 0px; font-size: 12px; -webkit-overflow-scrolling: touch;"><span class="hljs-class" style="line-height: 26px;"><span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">class</span> <span class="hljs-title" style="color: #c18401; line-height: 26px;">Solution</span>:</span><br> <span class="hljs-function" style="line-height: 26px;"><span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">def</span> <span class="hljs-title" style="color: #4078f2; line-height: 26px;">firstMissingPositive</span><span class="hljs-params" style="line-height: 26px;">(self, nums: List[int])</span> -&gt; int:</span><br> st = set()<br> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">if</span> len(nums) == <span class="hljs-number" style="color: #986801; line-height: 26px;">0</span>:<br> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">return</span> <span class="hljs-number" style="color: #986801; line-height: 26px;">1</span><br> <br> mini, maxi = <span class="hljs-number" style="color: #986801; line-height: 26px;">3e9</span>, <span class="hljs-number" style="color: #986801; line-height: 26px;">-3e9</span><br> <br> <span class="hljs-comment" style="color: #a0a1a7; font-style: italic; line-height: 26px;"># 插入set当中维护</span><br> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">for</span> i <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">in</span> nums:<br> st.add(i)<br> mini = min(mini, i)<br> maxi = max(maxi, i)<br> <br> <span class="hljs-comment" style="color: #a0a1a7; font-style: italic; line-height: 26px;"># 从1开始找到第一个不在set当中的元素</span><br> <span class="hljs-comment" style="color: #a0a1a7; font-style: italic; line-height: 26px;"># 由于nums只有n个元素,我们可以可以在n次遍历当中找到</span><br> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">for</span> i <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">in</span> range(<span class="hljs-number" style="color: #986801; line-height: 26px;">1</span>, maxi):<br> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">if</span> i <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">not</span> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">in</span> st:<br> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">return</span> i<br> <br> <span class="hljs-comment" style="color: #a0a1a7; font-style: italic; line-height: 26px;"># 如果从1到maxi都存在,那么就放回maxi+1和1的最大值</span><br> <span class="hljs-comment" style="color: #a0a1a7; font-style: italic; line-height: 26px;"># 因为如果maxi小于1,那么上面的循环不会执行,所以要和1取最大值</span><br> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">return</span> max(maxi+<span class="hljs-number" style="color: #986801; line-height: 26px;">1</span>, <span class="hljs-number" style="color: #986801; line-height: 26px;">1</span>)<br></code></pre> <h2 data-tool="mdnice编辑器" style="font-weight: bold; font-size: 24px; border-bottom: 2px solid rgb(89,89,89); margin-bottom: 50px; margin-top: 100px; color: rgb(89,89,89);"><span style="font-size: 22px; display: inline-block; border-bottom: 2px solid rgb(89,89,89);">in-place</span></h2> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">上面的两种做法一种进行了高复杂度的排序,另一种则用到了额外的存储。看起来这是一个两难问题,我们不想排序就需要用到存储,如果不想用存储呢,那么则需要元素有序。我们仔细分析一下这两种情况,就可以找到问题的症结了,我们有没有什么办法可以两全其美,<strong style="font-weight: bold; color: rgb(71, 193, 168);">既不用额外的存储又可以保证元素的有序呢</strong>?如果我们可以找到一种方法,那么这个问题就解决了。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">这也是我们解题的时候的一个常规的套路,就是对于一些题目而言有一些算法是比较明显的,但是可能因为这样或那样的限制使得并不能应用在当前的问题当中。但是没关系,我们一样可以往这方面去想,先找到一个不那么合适的解法,在此基础上谋求突破,很多时候要比凭空想出一个完美的方法来容易许多。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">那么我们怎么突破呢?</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">还要从题目的要求入手,题目当中规定只能使用常数的存储空间,意味着我们不能额外开辟数组或者其他容器来存储数据。有经验的同学可能已经反映过来了,这是<strong style="font-weight: bold; color: rgb(71, 193, 168);">in-place的套路</strong>。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">in-place并不是一个算法,而是一种思想。它出现的原因也非常简单,因为我们申请数组等容器的时候需要<strong style="font-weight: bold; color: rgb(71, 193, 168);">通过操作系统向内存申请连续的内存</strong>,这会涉及到一系列内存管理算法的执行,所以是需要<strong style="font-weight: bold; color: rgb(71, 193, 168);">消耗大量时间</strong>的。所以在一些高性能的场景下,我们会希望尽量避免空间申请操作。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">比如我们想要对数组进行排序,我们直接调用sorted方法的时候,其实在函数内部对数组进行了拷贝,最后返回的其实是拷贝数组排序之后的结果。也就是说我们<strong style="font-weight: bold; color: rgb(71, 193, 168);">获得的是一个新的数组</strong>,只是其中的元素和原来一模一样。而如果是in-place的方法,我们则不会另外创建数组,而在原数组上进行修改。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">非in-place的接口不会修改原值,这方便我们追踪数据的变化,以及撤销操作。比如Python机器学习领域的大量numpy和pandas的接口默认都不是in-place的,就是这个原因。而in-place的则相反,由于它会直接修改原值,所以如果我们一旦执行错了,无法撤销,原数据就找不回了。比如我们排序错了,明明要降序,不小心排成了升序,一旦执行就无法还原了。但是和非in-place相比,它的<strong style="font-weight: bold; color: rgb(71, 193, 168);">耗时更少,也更节约内存</strong>。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">这题其实已经暗示得很明显了,我们需要存储数据,但是又不让我们申请空间,于是我们只有in-place一条路可以走了。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">我们需要设计一个in-place的算法,让我们可以判断元素的存在性。再加上题目中的限制是正整数,而且我们要找的是第一个没有出现的正整数。如果数组的长度是n,那么其实我们可以锁定,<strong style="font-weight: bold; color: rgb(71, 193, 168);">答案一定在[1, n+1]之间</strong>。原因也很简单,因为最理想的情况是这个数组当中的n个元素刚好是1到n,这样我们从1开始遍历,一直找到n就能得到答案是n+1。否则的话,我们一定可以在遍历到n+1之前就找到答案,所以综合一下,答案一定在[1, n+1]之间。如果我们能把这个区间写出来,其实解法已经就在我们眼前了。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">既然答案在区间[1, n+1]中间,我们又需要设计一个in-place的方法,那么我们可以很正常地想到,我们可以<strong style="font-weight: bold; color: rgb(71, 193, 168);">将数字放到对应的下标当中去</strong>。1放到下标1当中,0放到0当中。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">比如[3, 1, 0, 5],我们拿到第一个元素是3,我们把它放到它应该在的位置,也就是5的位置下去,这个时候我们再来放5,由于5超过了数组的长度,所以进行丢弃。我们往下重复如上的过程,到最后的时候,我们得到的数据情况如下:[0, 1, 5, 3],我们遍历一下数组,发现和下标不匹配的位置就是5,它应该对应的数据是2,所以2就是答案。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">我一开始是先想到的算法,几乎是凭空想出来的,没有前后推导的过程,觉得非常惊艳,有种天马行空的感觉。后来关联上的in-place思想之后,才发现隐藏的思路其实非常合情合理。思路有了,代码真的很简单:</p> <pre class="custom" data-tool="mdnice编辑器" style="margin-top: 10px; margin-bottom: 10px;"><code class="hljs" style="overflow-x: auto; padding: 16px; color: #383a42; background: #fafafa; display: -webkit-box; font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; border-radius: 0px; font-size: 12px; -webkit-overflow-scrolling: touch;"><span class="hljs-class" style="line-height: 26px;"><span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">class</span> <span class="hljs-title" style="color: #c18401; line-height: 26px;">Solution</span>:</span><br> <span class="hljs-function" style="line-height: 26px;"><span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">def</span> <span class="hljs-title" style="color: #4078f2; line-height: 26px;">firstMissingPositive</span><span class="hljs-params" style="line-height: 26px;">(self, nums: List[int])</span> -&gt; int:</span><br> n = len(nums)<br> <span class="hljs-comment" style="color: #a0a1a7; font-style: italic; line-height: 26px;"># 因为是正整数,所以数组长度需要扩大1</span><br> nums.append(<span class="hljs-number" style="color: #986801; line-height: 26px;">0</span>)<br> <br> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">for</span> i <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">in</span> range(n):<br> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">if</span> i == nums[i]:<br> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">continue</span><br> <br> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">while</span> <span class="hljs-literal" style="color: #0184bb; line-height: 26px;">True</span>:<br> <span class="hljs-comment" style="color: #a0a1a7; font-style: italic; line-height: 26px;"># 不停地交换元素,直到范围超界或者是已经放好了为止</span><br> <span class="hljs-comment" style="color: #a0a1a7; font-style: italic; line-height: 26px;"># 需要考虑nums[i] 和 nums[nums[i]]相等的情况,这时候也不应该交换</span><br> val = nums[i]<br> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">if</span> val &gt; n <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">or</span> val &lt; <span class="hljs-number" style="color: #986801; line-height: 26px;">0</span> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">or</span> val == i <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">or</span> val == nums[val]:<br> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">break</span><br> nums[i], nums[val] = nums[val], val<br> <br> <br> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">for</span> i <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">in</span> range(<span class="hljs-number" style="color: #986801; line-height: 26px;">1</span>, n+<span class="hljs-number" style="color: #986801; line-height: 26px;">1</span>):<br> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">if</span> i != nums[i]:<br> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">return</span> i<br> <br> <span class="hljs-keyword" style="color: #a626a4; line-height: 26px;">return</span> n+<span class="hljs-number" style="color: #986801; line-height: 26px;">1</span><br> <br></code></pre> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">最后,我们来分析一下这个算法的复杂度,为什么我们在一重循环当中还套了一个while循环,但是它仍然是<span><img style="margin: 0 auto; width: auto; max-width: 100%; display: inline;" class="equation" src="https://juejin.im/equation?tex=O(n)" alt></span>的算法呢?</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">这个问题我们之前在介绍two pointers和尺取法的时候就曾经介绍过,我们在分析复杂度的时候<strong style="font-weight: bold; color: rgb(71, 193, 168);">不能只简单地看有几重循环</strong>,我们需要细致地分析。我们要忽略循环,回到问题的本质。我们用循环的本质是为了能够让每个元素放到对应的位置,一共需要安排的元素数量是固定的是n个,位置也是固定的是n个,一个元素只有一个位置。那么我们一次交换至少可以让一个元素放到正确的位置,那么问题来了,我们想要把所有元素放置好,需要循环多少次?</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">我这样问,大家应该很清楚,一次最少放一个,一共n个,显然最多放n次。那我们再看while循环当中,每执行一次,不就是放好了一个元素吗?外围的循环只是用来枚举元素的,并不会引入额外的计算,所以这当然是一个<span><img style="margin: 0 auto; width: auto; max-width: 100%; display: inline;" class="equation" src="https://juejin.im/equation?tex=O(n)" alt></span>的算法。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">最后,今天的题目官方标的难度是Hard,题目本身不难,由于加上了很多限制才提升了难度。今天的题目没有用到新的算法,纯粹是对思维和逻辑的考验。也因此,我觉得它是一道非常纯粹的题,纯粹在于它并用不到新的算法,也用不到新的数据结构,就是考察我们分析问题和思考问题的能力。而许多问题则针对性很强,如果之前没有学过对应的算法则无法做得出来,所以从这点上来说这题<strong style="font-weight: bold; color: rgb(71, 193, 168);">更加公平,非常适合面试</strong>。我已经进行了预约,以后如果有面试机会,我可能会问候选人这个问题。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89); margin-bottom: 25px;">今天的文章就是这些,如果觉得有所收获,请顺手点个<strong style="font-weight: bold; color: rgb(71, 193, 168);">关注或者转发</strong>吧,你们的举手之劳对我来说很重要。</p>

原文出处:https://www.cnblogs.com/techflow/p/12501792.html

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部