原題

解

第一步，萬(wàn)年不變的查錯(cuò)。如果給的array是null或空，直接return 0

    public int partitionArray(int[] nums, int k) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        ...
    }

這道題很簡(jiǎn)單，簡(jiǎn)直對(duì)不起medium難度。分明就是quickSort的第一步嘛?？偟膩?lái)說(shuō)，就是左右兩個(gè)pointer，左邊如果碰到大于等于k的，右邊如果碰到小于k的，那么就左右互換。最后return那個(gè)，可能需要想一下，要求nums[index]必須大于等于k。這個(gè)while loop的結(jié)束條件就是左邊超過(guò)右邊，所以其實(shí)左邊比右邊大，所以最后要return left;
直接上完整的code了，沒(méi)有難度。

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;
        int right = nums.length - 1;
        while (left <= right) {
            while (left <= right && nums[left] < k) {
                left++;
            }
            
            while (left <= right && nums[right] >= k) {
                right --;
            }
            
            if (left <= right) {
                swap(nums, left, right);
            }
        }
        
        return left;
    }
    
    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

分析

時(shí)間復(fù)雜度

只遍歷了一次，所以O(shè)(n)。

空間復(fù)雜度

O(1)。

總的來(lái)說(shuō)，太簡(jiǎn)單了。更簡(jiǎn)單的一種方法其實(shí)是一次遍歷，數(shù)比k小的數(shù)字有幾個(gè)，然后返回。如果真的面試碰到的話，應(yīng)該不要傻傻的直接two pointer。應(yīng)該先說(shuō)最明顯也是最簡(jiǎn)單的答案，然后等人家followup。