題目地址：https://leetcode-cn.com/problems/sort-colors/
題目描述：
給定一個包含紅色、白色和藍色，一共 n 個元素的陣列，原地對它們進行排序，使得相同顏色的元素相鄰，并按照紅色、白色、藍色順序排列，
此題中，我們使用整數 0、 1 和 2 分別表示紅色、白色和藍色，
示例：
輸入： [2,0,2,1,1,0]
輸出： [0,0,1,1,2,2]
解題思路：
??因為三個顏色的球用0、1、2來標識，按輸出0全部排在前面，2全部排在后面，初始化定義兩個下標位置min=0，指向最前面的位置，max=nums.length-1，指向陣列的最后一個下標，
??通過for回圈遍歷，如果是0就往前面移位，和min的下標互換，然后min+1，如果是2就往后移位，和max的下標位置互換，然后max-1，下一個2就要往前移，這時候互換位置之后，就需要判斷換到當前遍歷i的值是不是1了，如果不是1，就要回退i–，再遍歷，如果是1就放到這個位置，
class Solution {
public void sortColors(int[] nums) {
int numLength = nums.length;
int min = 0, max = numLength -1, temp;
//如果陣列只有0個或1個值，直接回傳
if(numLength <= 1){
return;
}
//移動0和2,1不移動
for(int i = 0; i <= max; ++i){
//如果等于0就放前面
if(nums[i] == 0){
temp = nums[i];
nums[i] = nums[min];
nums[min] = temp;
min++;
}
//等于2就往后面放，交換位置
if(nums[i] == 2){
temp = nums[i];
nums[i] = nums[max];
nums[max] = temp;
max--;
//判斷交換后的當前i下標的值，只有等于1不移動，回退重新回圈當前下標
if(nums[i] != 1){
--i;
}
}
}
//列印輸出結果
for (int i = 0; i < numLength; i++){
System.out.print(nums[i] + " ");
}
}
}
public class ColorType_75 {
public static void main(String[] args) {
int nums[] = {2,0,2,1,1,0,1,2,0,2,2,1,2,1,0,2,1,2,1,0,2};
Solution solution = new Solution();
solution.sortColors(nums);
}
}
運行結果：
??1 1 1 1 1 1 1 2 2 2 2 2 2 0 0 0 0 0 2 2 2
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/169192.html
標籤：其他
下一篇：Java變數及運算子