算法描述

給定一個(gè)數(shù)組和一個(gè)數(shù)k，劃分?jǐn)?shù)組，似的左邊的值都小于k，右邊的數(shù)大于等于k，返回劃分?jǐn)?shù)組的位置，例：[3, 2, 1] k = 1 --> 1, [2, 8, 3, 7] k = 9 --> 4

解題思路

參照快速排序算法，設(shè)左右兩個(gè)指針，如果左邊大于右邊，則交換，這里需要注意邊界問題，時(shí)間復(fù)雜度是O(n)

示例代碼

public int partitionArray(int[] nums, int k) {
        // write your code here
        if (nums.length <= 0) {
            return 0;
        } 
        int low = 0, high = nums.length - 1; 
        while(low < high) {
            while(nums[low] < k && (low < high)) {
                low++;
            }
            while(nums[high] >= k && (low < high)) {
                high--;
            }
            if (low < high) {
                int temp = nums[low];
                nums[low] = nums[high];
                nums[high] = temp;
                low++;
                high--;
            } 
        }
        if (nums[low] >= k) {
            return low;
        }
        return low + 1;
    }