基于快速排序的数组划分：2组 3组 K组（sort color）大小写排序 · Partition Array

2组：

［抄题］：

给出一个整数数组 nums 和一个整数 k。划分数组（即移动数组 nums 中的元素），使得：

所有小于k的元素移到左边
所有大于等于k的元素移到右边

返回数组划分的位置，即数组中第一个位置 i，满足 nums[i] 大于等于 k。

［思维问题］：

想不到两个小人的partition

［一句话思路］：

两个小人的partition，不用排序

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

直接调换就行了，不用写swap函数
要判断left < right，防止left加过头了
corner case别忘了

［总结］：

一直到left = right时都要一直处理，所以判断条件是left <= right。

［复杂度］：

Time complexity: 平均情况下，O(nlgn)每个数都放在一半中， Space complexity: O(lgn)放在一半中

［英文数据结构，为什么不用别的数据结构］：

降低复杂度

［其他解法］：

排序

［Follow Up］：

［题目变变变］：

/**
* 本参考程序来自九章算法，由 @九章算法 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/ 

public class Solution {
    /** 
     *@param nums: The integer array you should partition
     *@param k: As description
     *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++;
            }
            
            System.out.println("left++之后 = " + left);
            
            while (left <= right && nums[right] >= k) {
                right--;
            }
            System.out.println("right--之后 = " + right);

            //左边的数字太大，右边的数字太小的时候就换一下
            if (left <= right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                
                // left++;
                // right--;
                System.out.println("left又变了 = " + left);
                System.out.println("right又变了 = " + right);
            }
        }
        return left;
    }
}

View Code

3组：

［抄题］：

Given an array with n objects colored red, white, or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.You are not suppose to use the library's sort function for this problem.

［思维问题］：

［一句话思路］：

用partition，指定k，不用返回。结果就是小于k的数在左边，大于等于的在右边。

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

基于快速排序的数组划分：2组 3组 K组（sort color）大小写排序 · Partition Array

［一刷］：

nums[left] < k 时自加,因为前面有元素。会导致后面直接越出边界条件

［二刷］：

while移动的时候也要在if里保证没有超出边界
比较是分为两边，左右都是和边界比较

［总结］：

不是左小右大就要交换。

交换后的加减只是促进往前走罢了，防止TLE。

第一次交换之后要reset右边界。

一些个等号实在是太恶心了，就算了吧

［复杂度］：

Time complexity: 平均情况下，O(nlgn)每个数都放在一半中， Space complexity: O(lgn)放在一半中

［英文数据结构，为什么不用别的数据结构］：

［其他解法］：

遍历＋交换

［Follow Up］：

［题目变变变］：

class Solution {
    public void sortColors(int[] nums) {
        
        int left = 0;
        int right = nums.length - 1;
        while(left <= right) {
            //符合条件的
            while(left < right && nums[left] < 1) {
                left++;
            }
            while(left <= right && nums[right] >= 1) {
                right--;
            }
            System.out.println("left = " + left);
            System.out.println("right = " + right);
            
            //还是左边比右边小，说明符合条件的卡住了，没有完全进行。此时就需要交换
            if (left <= right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                
                left++;
                right--;
            }
        }
        
        right = nums.length - 1;
        while(left <= right) {
            while(left <= right && nums[left] < 2) {
                left++;
            }
            while(left <= right && nums[right] >= 2) {
                right--;
            }
            if (left <= right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                
                left++;
                right--;
            }
        }
    }
}

View Code

k组

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

public class Solution { /* * @param colors: A list of integer * @param k: An integer * @return: nothing */ public void sortColors2(int[] colors, int k) { // write your code here if (colors == null || colors.length == 0) { return; } rainbowSort(colors, 0, colors.length - 1, 1, k); } private void rainbowSort(int[] colors, int left, int right, int colors_left, int colors_right) { int l = left; int r = right; int colors_mid = (colors_left + colors_right) / 2; if (left >= right) { return ; } if (colors_left == colors_right) { return ; } while(l <= r) { while(l <= r && colors[l] <= colors_mid) { l++; } while(l <= r && colors[r] > colors_mid) { r--; } if (l <= r) { int temp = colors[r]; colors[r] = colors[l]; colors[l] = temp; l++; r--; } rainbowSort(colors,left,r,colors_left,colors_mid); rainbowSort(colors,l,right,colors_mid + 1,colors_right); } } }

/** * 本参考程序来自九章算法，由 @九章算法提供。版权所有，转发请注明出处。 * - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。 * - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班， * - Big Data 项目实战班，算法面试高频题班, 动态规划专题班 * - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code */ public class Solution { /** *@param nums: The integer array you should partition *@param k: As description *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++; } System.out.println("left++之后 = " + left); while (left <= right && nums[right] >= k) { right--; } System.out.println("right--之后 = " + right); //左边的数字太大，右边的数字太小的时候就换一下 if (left <= right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; // left++; // right--; System.out.println("left又变了 = " + left); System.out.println("right又变了 = " + right); } } return left; } }

class Solution { public void sortColors(int[] nums) { int left = 0; int right = nums.length - 1; while(left <= right) { //符合条件的 while(left < right && nums[left] < 1) { left++; } while(left <= right && nums[right] >= 1) { right--; } System.out.println("left = " + left); System.out.println("right = " + right); //还是左边比右边小，说明符合条件的卡住了，没有完全进行。此时就需要交换 if (left <= right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; } } right = nums.length - 1; while(left <= right) { while(left <= right && nums[left] < 2) { left++; } while(left <= right && nums[right] >= 2) { right--; } if (left <= right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; } } } }

基于快速排序的数组划分：2组 3组 K组（sort color）大小写排序 · Partition Array

相关推荐