e***s
发帖数: 799 | 1 求 Leetcode Online Judge Sort Color one pass constant space 解法。
Copy 下题目：
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.
Note:
You are not suppose to use the library's sort function for this problem.
Follow up:
A rather straight forward solution is a two-pass algorithm using counting
sort.
First, iterate the array counting number of 0's, 1's, and 2's, then
overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space? | j*****o
发帖数: 394 | 2 我写了个很丑的疑似ONE PASS....
我的小CASE是4 MILLI SEC
大CASE是 12 MILLI
if(n<=1) return;
int zeroptr=0;
int twoptr=n-1;
int i=0;
while(A[zeroptr]==0) zeroptr++;
while(A[twoptr]==2) twoptr--;
while(zeroptr<= twoptr && i<=twoptr){
if(i
switch(A[i]){
case 0: swap(A[zeroptr],A[i]); break;
case 1: i++; break;
case 2: swap(A[twoptr],A[i]); break;
default: break;
}
while(A[zeroptr]==0) zeroptr++;
while(A[twoptr]==2) twoptr--;
}
that
white
【在 e***s 的大作中提到】
: 求 Leetcode Online Judge Sort Color one pass constant space 解法。
: Copy 下题目：
: 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.
: Note:
: You are not suppose to use the library's sort function for this problem.
: Follow up:
| p*****2
发帖数: 21240 | 3 我写了一个练练
public void sortColors(int[] A)
{
int len=A.length;
int i=0;
int j=len-1;
int k=0;
while(k<=j)
{
if(A[k]==0)
swap(A,i++,k++);
else if(A[k]==2)
swap(A,k,j--);
else
k++;
}
} | l*****a
发帖数: 14598 | 4 编译通得过吗
【在 p*****2 的大作中提到】
: 我写了一个练练
: public void sortColors(int[] A)
: {
: int len=A.length;
: int i=0;
: int j=len-1;
: int k=0;
:
: while(k<=j)
: {
| e***s
发帖数: 799 | 5 2哥给力，我也想到了应该swap，但是就是脑子不好使。
【在 p*****2 的大作中提到】
: 我写了一个练练
: public void sortColors(int[] A)
: {
: int len=A.length;
: int i=0;
: int j=len-1;
: int k=0;
:
: while(k<=j)
: {
| e***s
发帖数: 799 | 6 妥妥的
【在 l*****a 的大作中提到】
: 编译通得过吗
|
|
