由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 求 Leetcode Online Judge Sort Color one pass constant space 解法
相关主题
iterator 实现 如何 peek(),pop()?Interview Question
问个经典问题的improvement~~问两道AMAZON电面题
收集了几个 List相关的题抛砖引玉:Careercup 150题中的错误
Uber 面经array contains two integer that sum up to 7
FB 上周2电面请教一个排序的问题
有些面试题是够扯蛋的2次电面后被amazon据了
求祝福, Google phone screen exposedamazon面试题目讨论贴
how to judge a linked list is palindrome?郁闷啊
相关话题的讨论汇总
话题: zeroptr话题: sort话题: twoptr话题: color话题: int
进入JobHunting版参与讨论
1 (共1页)
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 的大作中提到】
: 编译通得过吗
1 (共1页)
进入JobHunting版参与讨论
相关主题
郁闷啊FB 上周2电面
ValidNumber实在是不能不服如此简洁的解法有些面试题是够扯蛋的
问一道F家面试题求祝福, Google phone screen exposed
LeetCode Online Judge 的答案在哪里how to judge a linked list is palindrome?
iterator 实现 如何 peek(),pop()?Interview Question
问个经典问题的improvement~~问两道AMAZON电面题
收集了几个 List相关的题抛砖引玉:Careercup 150题中的错误
Uber 面经array contains two integer that sum up to 7
相关话题的讨论汇总
话题: zeroptr话题: sort话题: twoptr话题: color话题: int