LintCode 31. 数组划分

原题

解

第一步，万年不变的查错。如果给的array是null或空，直接return 0

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

这道题很简单，简直对不起medium难度。分明就是quickSort的第一步嘛。总的来说，就是左右两个pointer，左边如果碰到大于等于k的，右边如果碰到小于k的，那么就左右互换。最后return那个，可能需要想一下，要求nums[index]必须大于等于k。这个while loop的结束条件就是左边超过右边，所以其实左边比右边大，所以最后要return left;
直接上完整的code了，没有难度。

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;
    }
}

分析

时间复杂度

只遍历了一次，所以O(n)。

空间复杂度

O(1)。

总的来说，太简单了。更简单的一种方法其实是一次遍历，数比k小的数字有几个，然后返回。如果真的面试碰到的话，应该不要傻傻的直接two pointer。应该先说最明显也是最简单的答案，然后等人家followup。