Lintcode31 Partition Array solution題解

【題目描述】

Given an array nums of integers and an int k, partition the array (i.e move the elements in "nums") such that:All elements < k are moved to the left;All elements >= k are moved to the right;Return the partitioning index, i.e the first index i nums[i] >= k.

Notice:You should do really partition in array nums instead of just counting the numbers of integers smaller than k.If all elements in nums are smaller than k, then return nums.length

給出一個整數數組 nums 和一個整數 k。劃分數組（即移動數組 nums 中的元素），使得：所有小于k的元素移到左邊;所有大于等于k的元素移到右邊;返回數組劃分的位置，即數組中第一個位置 i，滿足 nums[i] 大于等于 k。

注意:你應該真正的劃分數組 nums，而不僅僅只是計算比 k 小的整數數，如果數組 nums 中的所有元素都比 k 小，則返回 nums.length。

【題目鏈接】

http://www.lintcode.com/en/problem/partition-array/

【題目解析】

容易想到的一個辦法是自左向右遍歷，使用right保存大于等于 k 的索引，i則為當前遍歷元素的索引，總是保持i >= right, 那么最后返回的right即為所求。

自左向右遍歷，遇到小于 k 的元素時即和right索引處元素交換，并自增right指向下一個元素，這樣就能保證right之前的元素一定小于 k. 注意if判斷條件中i >= right不能是i > right, 否則需要對特殊情況如全小于 k 時的考慮，而且即使考慮了這一特殊情況也可能存在其他 bug. 具體是什么 bug 呢？歡迎提出你的分析意見~

有了解過 Quick Sort 的做這道題自然是分分鐘的事，使用左右兩根指針 left,right 分別代表小于、大于等于 k 的索引，左右同時開工，直至 left>right.

大循環能正常進行的條件為 left<=right, 對于左邊索引，向右搜索直到找到小于 k 的索引為止；對于右邊索引，則向左搜索直到找到大于等于 k 的索引為止。注意在使用while循環時務必進行越界檢查！

找到不滿足條件的索引時即交換其值，并遞增left, 遞減right. 緊接著進行下一次循環。最后返回left即可，當nums為空時包含在left = 0之中，不必單獨特殊考慮，所以應返回left而不是right.

【參考答案】

http://www.jiuzhang.com/solutions/partition-array/