首页 > 代码库 > 75. Sort Colors

75. Sort Colors

2024-09-27 19:11:02   219人阅读

题目：

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.

链接： http://leetcode.com/problems/sort-colors/

5/29/2017

0ms, 62%

设3个下标，分别标志red, blue和当前遍历到的。red, blue所指的地方是下一个可以判断或者交换的位置。注意第10-14行也有交换的情况。并且第24行不需要index++

这种做法是通过中间的index来判断swap和更新其他两个下标的

 1 public class Solution {
 2     public void sortColors(int[] nums) {
 3         if (nums == null | nums.length == 0) return;
 4         
 5         final int red = 0, white = 1, blue = 2;
 6         int redIndex = 0, index = 0, blueIndex = nums.length - 1;
 7         
 8         while (index <= blueIndex) {
 9             if (nums[index] == red) {
10                 int tmp = nums[redIndex];
11                 nums[redIndex] = red;
12                 nums[index] = tmp;
13                 index++;
14                 redIndex++;
15             } else if (nums[index] == white) {
16                 index++;
17             } else {
18                 if (nums[blueIndex] == blue) {
19                     blueIndex--;
20                 } else {
21                     int tmp = nums[blueIndex];
22                     nums[blueIndex] = blue;
23                     nums[index] = tmp;
24                     blueIndex--;
25                 }
26             }
27         }
28         return;
29     }
30 }

别人的回答

比较好的解释

https://discuss.leetcode.com/topic/36832/sharing-c-solution-with-good-explanation

不需要swap的方法

算法特点，不使用if-else来判断，并且blue的index也是从前向后走的。根据的是当前k(blueIndex)的值来判断是否更新其他两个下标和是否更新这两个下标所指元素的值。

与swap方法的不同是，一个通过中间index判断，一个通过最右边index判断。注意细节。

https://discuss.leetcode.com/topic/26181/ac-python-in-place-one-pass-solution-o-n-time-o-1-space-no-swap-no-count

 1 def sortColors(self, nums):
 2     i = j = 0
 3     for k in xrange(len(nums)):
 4         v = nums[k]
 5         nums[k] = 2
 6         if v < 2:
 7             nums[j] = 1
 8             j += 1
 9         if v == 0:
10             nums[i] = 0
11             i += 1

更多讨论

https://discuss.leetcode.com/category/83/sort-colors

75. Sort Colors


联系
我们