Grokking the Coding Interview: Patterns for Coding Questions
See Grokking Pattern 1.
5. Pattern Cyclic Sort
这个cyclic sort,需要一点预备知识。cyclic sort条件是,数组元素必须是1到n,虽然乱序,但我们可以确定这个n长的数组里一定是1到n这n个数字,不会有别的数字。如果要对这种特别的数组排序,就可以环型排序,也可以叫圈排序。都知道1到n了还排序就很离谱,所以这并不是cyclic sort的使用场景。事实上,使用场景是Cyclic Sort这一题之外的题目。
Cyclic Sort (easy)
1 | Problem Statement |
这个题目着实惊呆我了,我遍历一遍直接将第i个元素改成i+1都通过测试。
不过老实做题的话,这个确实可以用cyclic sort做。cyclic sort具体步骤是,遍历,当当前的元素不在它应该在的位置时,把它和它应该在的那个位置的值做个交换,比如数组[4,3,2,1],当前看第一个元素4,它应该在最后,所以就交换一下,变成[1,3,2,4]。并且下一个要处理的元素还是当前,因为被交换了过来的元素可能也不是正确位置。
这个排序法的时间复杂度看起来很诡异,不知道怎么算。但可以这么考虑,因为我每一次swap,必然把一个元素放对位置了,所以swap次数最多就n-1次。因为n-1个元素位置对了,自然最后一个元素位置就对了,所以只有n-1次。
可以举个最差例子,[3,1,2]每个元素都不在正确位置。看3,swap后为[2,1,3],3就放对了,继续看2,swap后[1,2,3],由于2放对了,最后剩的一个元素就对了。
代码很好写,不用赘述。
但这个排序算法的意义何在呢?接下来的题目里可以提现。
Find the Missing Number (easy) – LeetCode
这个题目当然可以用cyclic sort做,但是需要注意,题目中是0-n少了某一个,然后乱序放在n长的数组里。假设缺少的那个数不是n,那么数组里就有n,上个题解中的cyclic sort,当然是不能把n这个数放对位置的,因为n长数组idx最大到n-1,没有n。
这怎么办呢?看了Coding Patterns: Cyclic Sort - emre.me就知道了,只需要忽略n就可以了,如果访问到n,就跳过n,往后访问。这样,遍历操作一遍后,就会出现,n在“不存在的那个数”的位置上,其他数都在对应的位置上。再遍历一次数组,就可以找到missing number了,显然如果遍历一遍数字都对,那么就是missing n这个数了。
这个题目有多种解法,bitmap等等,还能用数学的方法来做。但cyclic sort有一个好处,就是完全没有用额外空间。
Find all Missing Numbers (easy)
跟上题不一样了,输入n长的数组,里面就是1-n的某些,数字可重复,要输出all missing numbers。
但也容易做出来,拿example 1推演一遍就知道该怎么做了。把”错误位置的元素swap到正确位置“这一条规则不变,但如果有重复元素,就会出现nums[i]!=i and nums[nums[i]] == nums[i](意思是这么,但实际上idx从0到n-1,数值从1-n,代码里得偏移),此时nums[i]这个元素就是多余的,做一个特殊标记就行了,比如0或者-1,遍历中也要先ignore特殊值。于是missing numbers就是有特殊标记的那些,因为找不到值放在这些特殊位置上,说明这些值不存在。代码也简单,不多赘述。
同样,什么bitmap之类的都能做这个题,但cyclic sort可以O(n) and without extra space。
说代码简单,但也撞上错误了。主要是想节约空间,就直接拿nums[nums[i]]来swap,python swap a,b = b,a 也是有执行顺序的,nums[i]中途变了,最后结果反而是没有swap。很神奇。
algorithm - How swapping variables is implemented in Python? - Stack Overflow可以知道,a,b=b,a实际上是x1=a, x2=b,a=x2,b=x1,当然x1、x2是栈空间,还是需要auxiliary temporary locations。swap也没有magic。
不过还有一个点,就是swap这个写法,等式右边也是寻址才能拿到值,不是常量值,这里的规则是先把=右边算出来,详情见algorithm - python a,b = b,a implementation? How is it different from C++ swap function? - Stack Overflow。假设nums[i]值为v1,nums[nums[i]]值为v2,
nums[i], nums[nums[i]] = nums[nums[i]], nums[i]这一句会先拿出=右边的值,于是等价于nums[i], nums[nums[i]] = v2, v1。
然后这个时候才会真正找左边的地址,走x1,x2那一套交换。先找nums[i],找到了,然后赋值v2,然后nums[nums[i]]就是nums[v2],会把v1赋值给nums[v2]。
本来这个写法最多就是触发了错误的赋值,因为nums[v2]这个位置原本不应该参与进来。
但有趣的是,如果case比较巧合,碰上了v2==i,例如[2,1,0],取i=0,nums[i]=2,v1=2,nums[nums[i]]=0,v2=0,这就给循环上了。于是nums[i]先被赋值为v2,也就是nums[0]=0(v2),然后nums[v2]被赋值v1,也就是nums[0]=2,搞了半天,什么也没有变,nums[i]这个位置的值变了又变回来。
恰好我随便写的例子[4,3,2,1]完美符合。
而leetcode的case1 [4,3,2,7,8,2,3,1],也会死循环。举例说明,第一次交换时用的4和7(idx 0和3),即num[i], nums[nums[i]-1] = (7, 4),nums[0]=7,nums[7-1]=4,而第二次交换就要num[i], nums[nums[i]-1] = (4, 7),nums[0]=4, nums[4-1]=7,第三次交换则是num[i], num[nums[i]-1]=(7, 4),然后无限循环。这么说肯定很难懂,可以自己推演四五次交换,就会发现,由于第一次交换,无脑地使num[7-1]=4,导致之后,nums[4-1]和nums[7-1]就都不会变了,永远是7和4。然后nums[i]也就是nums[0]不是赋值为7就是赋值为4。
如果用nums[i]=v1,nums[v1]=v2来表示,假设nums[v2]可以访问,第一次交换后,nums[i]的值就会v1、v2反复横跳,nums[v1]永远=v2,nums[v2]永远=v1,虽然是(从1次开始计数)奇数次给v2赋值,偶数次给v1赋值,但第2次交换开始,给v1、v2赋的值永远一样,看起来就是永远不变。leetcode case1并没有太特别,只需要nums[v2]可以访问,就能永远死循环下去。
总之,一旦python swap的时候值是嵌套定位的,就要小心,最好避免swap里有嵌套。
Find the Duplicate Number (medium) – LeetCode
这个题目grokking和leetcode的要求不一样,grokking是不允许额外空间,但可以修改输入数组。leetcode则是不能修改输入数组,并且只是用常数量的额外空间。
grokking的限制下,当然还是cyclic sort了,sort途中就能发现重复的那一个数(题目说只有一个,发现后立刻返回就行了)。
leetcode的限制下,就不一样了,最简单当然是set/hash存,但不满足额外空间的限制。不能简单求和,因为他不是保证1到n都出现,而是只限制在[1, n]范围内,而且虽然只有一个数重复出现,但它可以出现2次以上。没有预备知识,很难想到这个题目可以用二分查找或者链表来解,链表还好说点,二分查找这个方法真有点过绕了,而且复杂度也要到nlogn,纯属脑筋急转弯。。。
不过确实也是个思路,而且不能直接套用基础版的二分查找,需要一定的改动,就算没改动,也需要证明可行性。整理了一下,没什么特别的坑,很容易做出来。算法设计期间需要注意,[left, right]这个搜索范围能不能缩小,如果某些情况不能缩小,自然不能最后缩小为最终答案一个值。
- 链表方法解这道题
Find all Duplicate Numbers (medium) – LeetCode
这一题grokking和leetcode要求类似了,grokking不允许额外空间(一些临时变量的栈空间肯定是允许的,不然代码都写不了),也就是常数量级的空间了。
这题用cyclic sort很容易做。因为题目保证了数字最多出现2次,“出现2次”在cyclic sort框架里是可以判断的,比如规则写为“出现一次的就在对应的位置上,当又想swap该值到对应位置,就说明该值第二次出现,该位置记为-2”,当你读到-2的时候就说明i这个值出现了2次。出现更多次也可以以此类推。cyclic sort可以说是完美的,不论统计出现几次的值,都可以做到。
但包括这个题和之前的题目,都有另一种常见做法。本质上是hash算法,因为通过自定义的hash,我们能把原数组变成hash桶,原来的nums内每一个位置都是一个数值,hash以后,nums每一个位置i都表示“数值i”出现的情况(这个情况实际当然是数字,而且由于是原地修改nums数组,这个“情况”是编码后的样子,得对应解码才能得出真实信息。)核心就是“编码规则”。设想下,如果你不编码,假设遇到i位置上值为x,你改了nums[x],并且不理会nums[x]原来位置的值,如果x大于i,你之后遍历到x位置时,就丢了这个数。所以必须编码,用一种方法,能够保留住原数值信息,同时也能存下这个位置i表示的数i出现了多少次。
最简单的做法就是+n+1,因为值最大到n,当你遍历数组时,发现i处的数值>n+1时,说明i值在前面出现过,而出现几次就相应+n+1,这样数值为x时,可以x//(n+1)得到出现次数,而x%(n+1)就可以得到i位置原始的数值,不会漏数。这就是一种编解码规则。
P.S. 也可以+n,当然,计算公式要跟着改变,[1,n]中如果取值n,求余就只能得到0了,所以值-1再求余,才可以。刚好,余数直接对应idx,+n+1的情况余数是真实数值,还得减一才能得到idx。
取反也是可以使用的编解码规则,出现一次就取反,但出现第二次还取反的话,就不行了,所以最多做到得出“出现两次”这个信息(都只能即时拿到,不能二次取反写入nums数组,这样跟一次没出现的情况就混在一次了),不可能辨别有没有出现第三次。
Problem Challenge 1 - Find the Corrupt Pair (easy)
1 | We are given an unsorted array containing ‘n’ numbers taken from the range 1 to ‘n’. The array originally contained all the numbers from 1 to ‘n’, but due to a data error, one of the numbers got duplicated which also resulted in one number going missing. Find both these numbers. |
题目不难,还是满足cyclic sort,但if-else有点多,不太简洁。因为我没有当发现duplicate number后即时保存,而是标记为-2,missing number则是标记为0。这样的算法,覆盖面更广,如果有多个duplicate或者missing number,都可以被查出来。但这个题已经明确说了dup和missing都只有一个,所以可以更简化一点。
回归最简单的cyclic sort,拿example推演一下,如果发现了nums[i]想要换到的位置已经有了,这个时候dup就知道了,但是这一次要不要swap?
举例说明,[1,2,3,2],当我们看到第二个2时,显然不能swap,会死循环。不swap,那怎么做呢?按前面的算法逻辑,就该把[i]这个位置标记为0或者什么。但这么做的话,又会增加if-else,因为下一次读[i]可能有0这个值了,必须单独考虑。
所以,再简单点,不swap,我也不操作了,就i+=1去搞下一个元素。这么做,是没问题的,很类似Find the Missing Number (easy)“n长的数组,是0到n这n+1个数缺了某个数”。Find the Missing Number (easy)的数组中可能有n,n是没办法交换到它应该在的位置的,所以放着就好了,它会在missing的那个位置上,或者整个数组都ok,n这个值就是missing的那一个。
再总结,例如[1,2,3,2]这个数组,我们忽略第二个2,那么数组最后的样子就是[1,2,3,2],再次遍历数组,i为3时[i]!=i+1,说明了什么?说明这个地方应该出现的值没在,所以i+1是missing number,而[i]==2,说明2是多的那个,所以[i]是dup number。
最后,再理解一下,这个题目其实和Find the Missing Number一模一样,因为dup和missing number都是通过错误的那一个位置可以得到。
代码见 https://gist.github.com/vagetablechicken/31b210446ec55944cb490c658c3c6a04
Problem Challenge 2 - Find the Smallest Missing Positive Number (medium)
1 | Given an unsorted array containing numbers, find the smallest missing positive number in it. |
这个题目简单一想,就是cyclic sort,sort完后第一个nums[i]!=i+1的地方就是the smallest missing positive number。但是要注意到(就算没注意到,example 3也过不了),nums中可能会出现>len+1的数,cyclic sort时也没办法把这种数放到“正确的位置”。再细想一下,总共就len这么多个数字,如果真就[1,len]每个数字出现一次,smallest missing positive number自然就只能是len+1了。所以,smallest missing positive number的取值范围只可能是[1,len+1],不会更大了。
Problem Challenge 3 - Find the First K Missing Positive Numbers (hard)
1 | Given an unsorted array containing numbers and a number ‘k’, find the first ‘k’ missing positive numbers in the array. |
看起来是挺简单的变种题目,但并不是。首先数组内元素没有限制,如果数组里存在>len的数,它是会影响结果的,不能直接忽略。
可以也先不管>len的数,但这样的结果就是,可以O(n)知道<=len的missing numbers,更大的missing numbers只能枚举,而且还得排除存在于nums数组里的,所以得有个set保存nums中存在的>len的数,每个数都要查一次是否存在,O(nlogn)。
这个>len的查询是省不掉的。参考答案里也是这个方法,简单朴实。
注意一下example1,因为它有重复的5和5,不能用最简单的
1 | while i<len: |
这么的话,经过几次swap,num[0]==5了,5想要被换到idx 4的地方,但恰好这里又是5,陷入死循环。
更好的逻辑是
1 | while i<len: |
因为nums[i]==i+1时,j就等于i,指向的同一个位置i,[i]!=[j]就可以判断了,还避免了重复情况。
其他坑,例如要保证output个数为k个等等都比较好修复。