FilesExpand file tree

 master

/

SortColors.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

66 lines (61 loc) · 1.63 KB

 master

/

SortColors.java

Top

File metadata and controls

• Code
• Blame

66 lines (61 loc) · 1.63 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

public class TwoPassSolution {

public void sortColors(int[] A) {

int zero = this.moveZeroToLeft(A);

this.moveTwoToRight(A, zero);

}

public void swap(int[] A, int slow, int fast) {

int temp = A[slow];

A[slow] = A[fast];

A[fast] = temp;

}

public int moveZeroToLeft(int[] A) {

int slow = 0;

int fast = 0;

while (fast < A.length) {

if (A[fast] == 0) {

this.swap(A, slow, fast);

slow += 1;

}

fast += 1;

}

return slow;

}

public void moveTwoToRight(int[] A, int zero) {

int slow = A.length - 1;

int fast = A.length - 1;

while (fast >= zero) {

if (A[fast] == 2) {

this.swap(A, slow, fast);

slow -= 1;

}

fast -= 1;

}

}

}

// My previous solution is actually two passes.

// Here's one pass solution from:

// http://fisherlei.blogspot.com/2013/01/leetcode-sort-colors.html

public class OnePassSolution {

public void sortColors(int[] nums) {

int red = 0;

int blue = nums.length - 1;

int i = 0;

while (i < blue + 1) {

if (nums[i] == 1) {

i ++;

} else if (nums[i] == 2) {

swap(nums, i, blue);

blue --;

} else {

swap(nums, i, red);

red ++;

i ++;

}

}

}

public void swap(int[] nums, int i, int j) {

int temp = nums[i];

nums[i] = nums[j];

nums[j] = temp;

}

}