程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode筆記:Sort Colors

leetcode筆記:Sort Colors

編輯:關於C++

一. 題目描述

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?

二. 題目分析

題目一開始說到一組對象,包含紅白藍三種顏色,然後要對他們進行排序,說白了就是對一個只含有0, 1, 2三個數字的數組從小到大排序。

題目要求:come up with an one-pass algorithm using only constant space,因此只能掃描一次。這裡采取的方法是,統計0, 1, 2三個數字分別出現的次數,再將數組nums重新構建為從0到2排列的數組,這種方法沒有使用數組元素間的交換,只需掃描一次nums。

三. 示例代碼

#include 
#include 

using namespace std;

class Solution {
public:
    void sortColors(vector& nums) 
    {
        int SIZE = nums.size();
        int count[3] = {0, 0, 0};
        for (int i = 0; i < SIZE; ++i)
            ++count[nums[i]];

        for (int i = 0, index = 0; i < 3; ++i)
            for (int j = 0; j < count[i]; ++j)
                nums[index++] = i;
    }
};

一個測試結果:

這裡寫圖片描述

四. 小結

本題的解法還是挺多的,可多參考網上的其他解法。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved