144.Interleaving Positive and Negative Numbers

这道题就不说把正负数保存起来然后再合并的算法了,挑战是完成inplace地变换。

这里要用的是QuickSort相关的技巧。或者说QuickSelect,然后就是对不同情况的判断来cover所有情况。 首先说下思路,就是按照QuickSelect的想法。先inplace地把负数全挪在左边,正数右边。然后再利用类似数组reverse的思路来调整,关键是指针一次走两个位置,这样保证了可以一正一负间隔

  1. 按照题意应该是不应该有0的,有0会稍微影响我们的思路。问清楚面试官是不是可以有这个假设,如果真的有0,是当正数还是负数?
  2. 还有一个要问清楚的就是如果数组根本没办法可以间隔分配怎么办。原题由于是返回void,感觉上是默认了肯定有解。但是还是应该去cover这个情形。好了下面都是假设有解的情况-->
  3. 首先如果长度是偶数,即正负数一样多,就不存在谁多谁少情况。对于正负数一个多一个少的情况。网上有很多解释,又是要反转数组又是要移动数字的。起始那些都很麻烦。不用那么费劲,只要把不同情形考虑清楚就好了。比如得出来正数多,那么就应该让最后的置换的循环的left为0,right为len-2。即最后一个我仍在哪里不管了。反之如果负数多,left为1而right为len-1就好了。剩下就是while(left<right) 循环去吧!
  4. 怎么判断右边多还是少?我用的是第一次QuickSelect循环下来剩下的left的index即右边一侧的第一个元素的index来得知长度地判断。记得把这个left存起来,我第一次就没存,结果后来left值修改了以后我还拿这个变量来分析长度呢,傻傻地犯错。
Show your support

Clapping shows how much you appreciated DeReK’s story.