1. 解题思路
这一题挺简单的,就是一个分组进行排序考察,我们将相邻且bit set相同的元素划归到同一组,然后进行排序,然后依次看各个组之间是不是都满足有序关系即可。
2. 代码实现
给出python代码实现如下:
class Solution:
def canSortArray(self, nums: List[int]) -> bool:
n = len(nums)
def count_digit(num):
return Counter(bin(num)[2:])["1"]
idx = 0
pre_max = -1
while idx < n:
elems = []
d = count_digit(nums[idx])
while idx < n and count_digit(nums[idx]) == d:
elems.append(nums[idx])
idx += 1
elems = sorted(elems)
if elems[0] < pre_max:
return False
pre_max = elems[-1]
return True
提交代码评测得到:耗时143ms,占用内存16.7MB。