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太少了 没东西能看