leetcode75之顏色分類
題目描述：
給定一個包含紅色、白色和藍色，一共 n 個元素的數組，原地對它們進行排序，使得相同顏色的元素相鄰，並按照紅色、白色、藍色順序排列。
此題中，我們使用整數 0、 1 和 2 分別表示紅色、白色和藍色。
注意:
不能使用程式碼庫中的排序函數來解決這道題。
不能使用程式碼庫中的排序函數來解決這道題。
示例:
輸入: [2,0,2,1,1,0] 輸出: [0,0,1,1,2,2]
來源：力扣（LeetCode）
鏈接：//leetcode-cn.com/problems/sort-colors
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。
鏈接：//leetcode-cn.com/problems/sort-colors
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。
實現如下：
1 def sortColors(nums): 2 ''' 3 使用計數排序思想 4 :param nums: 5 :return: 6 ''' 7 colors = [0] * 3 8 9 for i in nums: 10 colors[i] += 1 11 12 j = 0 13 for m in range(3): 14 for n in range(colors[m]): # 控制次數 15 nums[j] = m 16 j += 1 17 18 return nums 19 20 21 print('==============測試colorsort()============') 22 nums = [2, 1, 1, 0, 2, 1] 23 result = sortColors(nums) 24 print("result=", result) 25 26 27 def bubbleSort(nums): 28 ''' 29 實現冒泡排序 30 :param nums: 31 :return: 32 ''' 33 34 for i in range(len(nums) - 1): # 控制循環次數 35 for j in range(len(nums) - i - 1): # 控制每次循環時在指定數組長度內進行 36 if nums[j] > nums[j + 1]: 37 nums[j], nums[j + 1] = nums[j + 1], nums[j] 38 else: 39 continue 40 41 return nums 42 43 44 print("----------------測試Bubblesort()-------------") 45 nums = [2, 1, 3, 5, 6, 2, 0, 2, 0, 2] 46 result = bubbleSort(nums) 47 print("result=", result) 48 49 50 def colorsort1(nums): 51 ''' 52 使用桶排序思想 53 :param nums: 54 :return: 55 ''' 56 color = [[] for i in range(3)] 57 for i in nums: 58 color[i].append(i) 59 60 nums[:] = [] 61 62 for i in color: 63 nums.extend(i) 64 65 return nums 66 67 68 print("-----------測試colorsort1()------------") 69 nums = [2, 1, 2, 1, 0, 1, 0, 0, 2] 70 result = colorsort1(nums) 71 print("result=", result) 72 73 74 def colorsort2(nums): 75 ''' 76 荷蘭三色旗問題 77 :param nums: 78 :return: 79 ''' 80 p0 = curr = 0 81 p2 = len(nums) - 1 82 83 while curr <= p2: 84 if nums[curr] == 0: 85 nums[p0], nums[curr] = nums[curr], nums[p0] 86 p0 += 1 87 curr += 1 88 elif nums[curr] == 2: 89 nums[curr], nums[p2] = nums[p2], nums[curr] 90 p2 -= 1 91 else: 92 curr += 1 93 94 return nums 95 96 97 print("------------測試colorsort2()--------------") 98 nums = [2, 0, 2, 0, 0, 1, 1, 1] 99 result = colorsort2(nums) 100 print("result=", result)
輸出：
==============測試colorsort()============ result= [0, 1, 1, 1, 2, 2] ----------------測試Bubblesort()------------- result= [0, 0, 1, 2, 2, 2, 2, 3, 5, 6] -----------測試colorsort1()------------ result= [0, 0, 0, 1, 1, 1, 2, 2, 2] ------------測試colorsort2()-------------- result= [0, 0, 0, 1, 1, 1, 2, 2]
總結：上述一共採用四種方法解決該問題。四種方法使用不同的思想方法。這裡需要說明一下最後一種荷蘭三色旗採用的三指針方法。初始化三個指針分別為p0,curr和p2,p0初始化為指向第一個元素，p2指向最後一個元素，curr指針用來遍歷整個數組，指向當前元素，所以初始化也為0。當指向元素為0時，交換當前元素和p0,當指向元素為2時，交換當前元素和p2,再緊接著判斷當前元素的值，程式碼中表現為curr不增加。
