# Partition Array ### Source - [(31) Partition Array](http://www.lintcode.com/en/problem/partition-array/) ~~~ 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. Example If nums=[3,2,2,1] and k=2, a valid answer is 1. Note 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 Challenge Can you partition the array in-place and in O(n)? ~~~ ### 題解1 - 自左向右 容易想到的一個辦法是自左向右遍歷，使用`right`保存大于等于 k 的索引，`i`則為當前遍歷元素的索引，總是保持`i >= right`, 那么最后返回的`right`即為所求。 ### C++ ~~~ class Solution { public: int partitionArray(vector<int> &nums, int k) { int right = 0; const int size = nums.size(); for (int i = 0; i < size; ++i) { if (nums[i] < k && i >= right) { int temp = nums[i]; nums[i] = nums[right]; nums[right] = temp; ++right; } } return right; } }; ~~~ ### 源碼分析 自左向右遍歷，遇到小于 k 的元素時即和`right`索引處元素交換，并自增`right`指向下一個元素，這樣就能保證`right`之前的元素一定小于 k. 注意`if`判斷條件中`i >= right`不能是`i > right`, 否則需要對特殊情況如全小于 k 時的考慮，而且即使考慮了這一特殊情況也可能存在其他 bug. 具體是什么 bug 呢？歡迎提出你的分析意見~ ### 復雜度分析 遍歷一次數組，時間復雜度最少為 O(n)O(n)O(n), 可能需要一定次數的交換。 ### 題解2 - 兩根指針 有了解過 [Quick Sort](http://algorithm.yuanbin.me/zh-cn/basics_sorting/quick_sort.html) 的做這道題自然是分分鐘的事，使用左右兩根指針 left,rightleft, rightleft,right 分別代表小于、大于等于 k 的索引，左右同時開工，直至 left>rightleft > rightleft>right. ### C++ ~~~ class Solution { public: int partitionArray(vector<int> &nums, int k) { int left = 0, right = nums.size() - 1; while (left <= right) { while (left <= right && nums[left] < k) ++left; while (left <= right && nums[right] >= k) --right; if (left <= right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; ++left; --right; } } return left; } }; ~~~ ### 源碼分析 大循環能正常進行的條件為 left<=rightleft <= rightleft<=right, 對于左邊索引，向右搜索直到找到小于 k 的索引為止；對于右邊索引，則向左搜索直到找到大于等于 k 的索引為止。注意在使用`while`循環時務必進行越界檢查！ 找到不滿足條件的索引時即交換其值，并遞增`left`, 遞減`right`. 緊接著進行下一次循環。最后返回`left`即可，當`nums`為空時包含在`left = 0`之中，不必單獨特殊考慮，所以應返回`left`而不是`right`. ### 復雜度分析 只需要對整個數組遍歷一次，時間復雜度為 O(n)O(n)O(n), 相比題解1，題解2對全小于 k 的數組效率較高，元素交換次數較少。 ### Reference - [Partition Array | 九章算法](http://www.jiuzhang.com/solutions/partition-array/)