https://leetcode.com/problems/find-if-array-can-be-sorted 3011. Find if Array Can Be Sorted 給一個 0 索引的正整數數組 nums 如果任兩個相鄰元素的 set-bits 數量相同 則可以進行交換 回傳 true 如果可以排序這個數組 否則就回傳 false Example 1: Input: nums = [8,4,2,30,15] Output: true Explanation: 5個數的二進位表示分別是 1000 100 10 11110 1111 前3個數的 set-bits 都是 1 所以3個之間可以交換排序 變成 2,4,8 後2個數則都是 4 也可以交換排序 變成 15,30 合起來就是 2,4,8,15,30 成功進行排序 Example 2: Input: nums = [1,2,3,4,5] Output: true Explanation: 已經是排序過的 回傳 true Example 3: Input: nums = [3,16,8,4,2] Output: false Explanation: 3 是 "11" 其他的 set-bits 都是 1 無法變成排序後的數組 false Constraints: 1 <= nums.length <= 100 1 <= nums[i] <= 2^8 思路1： 先用一個for循環將相鄰間相同 set-bits 的數放在一起 之後再用一次for判斷前數組的最大值是否小於後數組的最小值 思路2比較好 不過先寫第一次通過的code Python Code: class Solution: def canSortArray(self, nums: List[int]) -> bool: if nums == sorted(nums): return True # 發現一行的if寫法似乎總是比換行慢 所以現在都換行寫 array = [[nums[0]]] cnt = bin(nums[0]).count('1') for i in nums[1:]: if bin(i).count('1') != cnt: array.append([i]) cnt = bin(i).count('1') else: array[-1].append(i) for n in range(len(array)-1): if max(array[n]) > min(array[n+1]): return False return True 思路2： 改在cnt不同時就判斷 就不用多開一個array 只要記錄前一組當中的最大值就好 然後發現在3.10有多一個 int.bit_count() 直接回傳數量 就不用自己計算 set-bits 然後記得for循環完後也要判斷一次大小 Python Code: class Solution: def canSortArray(self, nums: List[int]) -> bool: cnt = nums[0].bit_count() prev_max = 0 # 最小值是1 temp = [nums[0]] for i in nums[1:]: if i.bit_count() == cnt: temp.append(i) elif prev_max > min(temp): return False else: prev_max = max(temp) temp = [i] cnt = i.bit_count() if prev_max > min(temp): return False return True 今天思路1想了快一個小時 到思路2又一個多小時 好爛 (( bit_count()是看0ms的Code Sample發現的 不過它跟思路1類似 用2個for 我猜是之前測資比較少 現在測資有999個 ( 然後我把思路2轉成JavaScript 但Runtime的data太少了 沒東西能看 -- ※ 發信站: 批踢踢實業坊(ptt-club.com.tw), 來自: 114.45.20.205 (臺灣) ※ 文章網址: https://ptt-club.com.tw/Marginalman/M.1730868043.A.481