描述
給出一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù)k劃分?jǐn)?shù)組（即移動(dòng)數(shù)組 nums 中的元素）显蝌，使得：
所有小于k的元素移到左邊
所有大于等于k的元素移到右邊
返回?cái)?shù)組劃分的位置，即數(shù)組中第一個(gè)位置 i毛萌，滿足 nums[i] 大于等于 k
注意事項(xiàng)
你應(yīng)該真正的劃分?jǐn)?shù)組 nums卦尊，而不僅僅只是計(jì)算比k小的整數(shù)恋拷，如果數(shù)組 nums 中的所有元素
都比k小泊藕，則返回 nums.length已骇。
挑戰(zhàn)
使用 O(n) 的時(shí)間復(fù)雜度在數(shù)組上進(jìn)行劃分闭翩。
思路
值得注意的地方是在快速排序算法的各種應(yīng)用中误债，下面四個(gè)連續(xù)判斷條件要一致浸船，此算法left不能等于right，在快排中分割值是在數(shù)組中挑的寝蹈，本題中數(shù)組元素可能都小于k糟袁，可能出現(xiàn)left等于right且在邊界點(diǎn)仍滿足條件，left++越界的情形
比如數(shù)組[7,7,9,8,6,6,8,7,9,8,6,6]躺盛，k = 10
代碼
public class Solution {
/*
* @param nums: The integer array you should partition
* @param k: An integer
* @return: The index after partition
*/
public int partitionArray(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return 0;
}
int left = 0, right = nums.length - 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--;
}
}
// left = right 情況單獨(dú)判斷，本題之所以在上面的 while 循環(huán)中把 = 去掉形帮，
// 是由于題目要求返回?cái)?shù)組中第一個(gè)位置 i 滿足 nums[i] 大于等于 k
// 上述代碼已經(jīng)完成了基本的 partition 功能槽惫，但分割點(diǎn) left = right 處值和 k 的大小關(guān)系要特判下
// 此處還可能出現(xiàn) left 和 right 由于 ++ -- 操作后剛好錯(cuò)開的情形周叮，但下面代碼也可以返回正確結(jié)果
if (nums[left] >= k) {
return left;
}
return left + 1;
}
}
