sortColors

Given an array with n objects colored red, white or blue, sort them in-place 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.

Note: You are not suppose to use the library's sort function for this problem.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-colors
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法1：遍历元素，把0调到数组的前面，把2调到数组后面，1不用处理：

 public void sortColors(int[] nums) {

        int length = nums.length;

        int temp,index;

        index=0;

        for(int i = 0; i < length; i++)

        {

            if(nums[i] == 0)

            {

                temp = nums[index];

                nums[index++] = nums[i];

                nums[i] = temp;

            }

        }

        index=length - 1;
//这里其实可以加个限定条件，因为是从数组末端开始遍历的，当遍历到0的时候，就已经不用再往前遍历了，因此也可节省一丁点时间，不过好像问题并不大，需要优化的是内存方面。。。

        for(int j = length - 1; j >= 0; j--)

        {

           if(nums[j] == 2)

            {

                temp = nums[index];

                nums[index--] = nums[j];

                nums[j] = temp;

            }

        }

    }

解法2：遍历计数0,1,2的个数，再把原数组重新赋值：

    public void sortColors(int[] nums) {

        int length = nums.length;

        int count = 0;

        int count1 = 0;

        int count2;

        for(int i = 0; i < length; i++)

        {

            if(nums[i] == 0)

            {

                nums[count] = 0;

                count++;

            }

            else if(nums[i] == 1)

            {

                count1++;

            }

        }

        count2 = length - (count + count1);

        for(int i = count; i < count + count1; i++)

        {

            nums[i] = 1;

        }

        for(int i = count+count1; i < length; i++)

        {

            nums[i] = 2;

        }

    }

巴特西

sortColors

最新文章

热门文章