Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitf81c713

Browse files
author
applewjg
committed
SortColors I && II
Change-Id: I333d915b135f867703e379f4c61fe80bbc29c088
1 parent81e067a commitf81c713

File tree

2 files changed

+92
-0
lines changed

2 files changed

+92
-0
lines changed

‎SortColors.java

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
/*
2+
Author: King, wangjingui@outlook.com
3+
Date: Dec 24, 2013
4+
Problem: Sort Colors
5+
Difficulty: Medium
6+
Source: https://oj.leetcode.com/problems/sort-colors/
7+
Notes:
8+
Given an array with n objects colored red, white or blue, sort them so that objects of the same color
9+
are adjacent, with the colors in the order red, white and blue.
10+
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
11+
Note:
12+
You are not suppose to use the library's sort function for this problem.
13+
Follow up:
14+
A rather straight forward solution is a two-pass algorithm using counting sort.
15+
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with
16+
total number of 0's, then 1's and followed by 2's.
17+
Could you come up with an one-pass algorithm using only constant space?
18+
19+
Solution: 0 0 0 1 1 1 1 ...... 2 2 2 2
20+
| | |
21+
zero i two
22+
-> -> <-
23+
*/
24+
publicclassSolution {
25+
publicvoidsortColors(int[]A) {
26+
intn =A.length;
27+
if (n <=1)return;
28+
for (inti =0,left =0,right =n -1;i <=right;) {
29+
if (A[i] ==0) {
30+
A[i++] =A[left];
31+
A[left++] =0;
32+
}elseif (A[i] ==2) {
33+
A[i] =A[right];
34+
A[right--] =2;
35+
}elsei++;
36+
}
37+
}
38+
}

‎SortColorsII.java

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
/*
2+
Author: King, wangjingui@outlook.com
3+
Date: Dec 24, 2013
4+
Problem: Sort Colors
5+
Difficulty: Medium
6+
Source: http://lintcode.com/zh-cn/problem/sort-colors-ii/
7+
Notes:
8+
Given an array of n objects with k different colors (numbered from 1 to k), sort them so that objects of the same color are adjacent, with the colors in the order 1, 2, ... k.
9+
10+
Note
11+
You are not suppose to use the library's sort function for this problem.
12+
13+
Example
14+
GIven colors=[3, 2, 2, 1, 4], k=4, your code should sort colors in-place to [1, 2, 2, 3, 4].
15+
16+
Challenge
17+
A rather straight forward solution is a two-pass algorithm using counting sort. That will cost O(k) extra memory.
18+
19+
Can you do it without using extra memory?
20+
21+
Solution: Use the first k buckets to store the count. (count sort, two pass).
22+
*/
23+
classSolution {
24+
/**
25+
* @param colors: A list of integer
26+
* @param k: An integer
27+
* @return: nothing
28+
*/
29+
publicvoidsortColors2(int[]A,intk) {
30+
// write your code here
31+
intn =A.length;
32+
if (n <=1)return;
33+
for (inti =0;i <n; ++i) {
34+
if(A[i] >0) {
35+
intc =A[i];
36+
A[i] =0;
37+
while(true) {
38+
if (A[c-1] <=0) {
39+
--A[c-1];
40+
break;
41+
}else {
42+
intcol =A[c-1];
43+
A[c-1] = -1;
44+
c =col;
45+
}
46+
}
47+
}
48+
}
49+
intidx =n;
50+
for (inti =k;i >0; --i) {
51+
for (intj =0;j >A[i-1]; --j)A[--idx] =i;
52+
}
53+
}
54+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp