Sort Colors-K6K4.com

原题： https://leetcode.com/problems/sort-colors/description/
题意： 对一个包含0,1,2三种数字的数组重新排序，使得排好序的数组前一段都是0，中间一段都是1，最后一段都是2。
约定：（1）不能使用库函数的排序功能来解决这个问题。

标签： colors、一段、排序功能、sort、排好序、面试

猜你感兴趣的圈子：

LeetCode交流圈

Bingo

2017-08-11 11:44:36 1楼#1层

扫描两遍的计数排序：

public class Solution {  
    public void sortColors(int[] A) {  
        int i, r, w, b;  
        r = w = b = 0;  
        for (i = 0; i < A.length; i++) {  
            if (A[i] == 0) r++;  
            else  if (A[i] == 1) w++;  
            else b++;  
        }  
        for (i = 0; i < A.length; i++) {  
            if (i < r) A[i] = 0;  
            else if (i < r + w) A[i] = 1;  
            else A[i] = 2;  
        }  
    }  
}

Bingo

2017-08-11 11:45:06 2楼#1层

扫描一遍，双向遍历：

public class Solution {  
    public void swap(int[] A, int a, int b) {  
        int tmp = A[a];  
        A[a] = A[b];  
        A[b] = tmp;  
    }  
      
    public void sortColors(int[] A) {  
        int len = A.length;  
        int i, j, r, w, b;  
        i = 0;  
        j = len - 1;  
        r = b = 0;  
        while (i <= j) {  
            if (A[i] == 0) {  
                swap(A, i, r);  
                i++;  
                r++;  
                continue;  
            }  
            if (A[j] == 2) {  
                swap(A, j, len-1-b);  
                j--;  
                b++;  
                continue;  
            }  
            if (A[j] == 0) {  
                swap(A, i, j);  
                continue;  
            }  
            if (A[i] == 2) {  
                swap(A, i, j);  
                continue;  
            }  
            //如果上述任何情况都不满足，那么只有下面一种可能  
            //if (A[i] == 1 && A[j] == 1) {  
                i++;  
                j--;  
            //}  
        }  
    }  
}

Bingo

2017-08-11 11:45:36 3楼#1层

扫描一遍，单项遍历：

public class Solution {  
    public void swap(int[] A, int a, int b) {  
        int tmp = A[a];  
        A[a] = A[b];  
        A[b] = tmp;  
    }  
      
    public void sortColors(int[] A) {  
        int len = A.length;  
        int i, r = 0, b = 0;  
        for (i = 0; i < len-b; i++) {  
            if (A[i] == 0) {  
                swap(A, i, r);  
                r++;  
            } else if (A[i] == 2) {  
                swap(A, i, len-1-b);  
                b++;  
                i--; //后面交换过来的元素也要进行判断  
            }   
        }  
    }  
}

取消

回复

推荐圈子

LeetCode交流圈