專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

最近在網上看到有人做了一個統計，統計的是中國最難入職的IT公司，排名第一的是拼多多，拼多多需要處理高并發和分布式系統，技術挑戰大，面試流程可能包括多輪技術面和系統設計，同時工作壓力導致篩選更嚴。我現在網上購物也會使用拼多多，雖然很多東西質量不怎么樣，但人家便宜。之前我一直以為字節跳動應該是最難的，畢竟字節算法考的比較難，基本上都是hard級別的。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第75題：顏色分類。

問題描述

來源：LeetCode第75題

難度：中等

給定一個包含紅色、白色和藍色、共 n 個元素的數組 nums ，原地對它們進行排序，使得相同顏色的元素相鄰，并按照紅色、白色、藍色順序排列。

我們使用整數 0、 1 和 2 分別表示紅色、白色和藍色。必須在不使用庫內置的 sort 函數的情況下解決這個問題。

示例1：

輸入：nums = [2,0,2,1,1,0] 輸出：[0,0,1,1,2,2]

示例2：

輸入：nums = [2,0,1] 輸出：[0,1,2]

• n == nums.length

• 1 <= n <= 300

• nums[i] 為 0、1 或 2

問題分析

這題是讓把數組中的 0 都挪到前面，2 都挪到后面，1 放到中間，其實就是荷蘭國旗問題，解決方式也比較簡單 。

我們可以使用三個指針，left指向前面需要交換的元素，right指向后面需要交換的元素，還一個index指向當前遍歷的元素。

如果index指向的元素是 0 ，就和left指向的元素交換，交換完之后left要往后移一步。同理如果index指向的元素是 2 ，就和right指向的元素交換，交換完之后right要往前移一步。否則index指向的就是 1 ，不需要做任何交換。

這里要注意index指向的值和left指向的值交換之后，index是可以往后移一步的。但index和right指向的值交換之后，index是不能往后移的，因為在交換之前，right指向的值有可能是0或者是2，所以交換之后還需要再次計算。

JAVA：

public void sortColors(int[] nums) {     int left = 0;// 0的右邊界     int right = nums.length - 1;// 2的左邊界     int index = 0;// 指向當前數字     while (index <= right) {         if (nums[index] == 0) {             // 如果是0，就往前面移             swap(nums, left++, index++);         } else if (nums[index] == 1) {             // 如果是1，不做任何交換             index++;         } else if (nums[index] == 2) {             // 如果是2就往后面移             swap(nums, right--, index);         }     } } // 交換數組中的兩個數字 private void swap(int[] nums, int i, int j) {     int tmp = nums[i];     nums[i] = nums[j];     nums[j] = tmp; }

C++：

public:     void sortColors(vector

  &nums) {         int left = 0;// 0的右邊界         int right = nums.size() - 1;// 2的左邊界         int index = 0;// 指向當前數字         while (index <= right) {             if (nums[index] == 0) {                 // 如果是0，就往前面移                 swap(nums[left++], nums[index++]);             } else if (nums[index] == 1) {                 // 如果是1，不做任何交換                 index++;             } else if (nums[index] == 2) {                 // 如果是2就往后面移                 swap(nums[right--], nums[index]);             }         }     }

C：

void swap(int *a, int *b) {     int tmp = *a;     *a = *b;     *b = tmp; } void sortColors(int *nums, int numsSize) {     int left = 0;// 0的右邊界     int right = numsSize - 1;// 2的左邊界     int index = 0;// 指向當前數字     while (index <= right) {         if (nums[index] == 0) {             // 如果是0，就往前面移             swap(&nums[left++], &nums[index++]);         } else if (nums[index] == 1) {             // 如果是1，不做任何交換             index++;         } else if (nums[index] == 2) {             // 如果是2就往后面移             swap(&nums[right--], &nums[index]);         }     } }

Python：

def sortColors(self, nums: List[int]) -> None:     # left 是0的右邊界，right是2的左邊界，index是指向當前數字。     left, right, index = 0, len(nums) - 1, 0     while index <= right:         if nums[index] == 0:             # 如果是0，就往前面移             nums[left], nums[index] = nums[index], nums[left]             left += 1             index += 1         elif nums[index] == 1:             # 如果是1，不做任何交換             index += 1         elif nums[index] == 2:             # 如果是2就往后面移             nums[right], nums[index] = nums[index], nums[right]             right -= 1

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。