JZX轻语：简
LeetCode 3011 - 判断一个数组是否可以变为有序
发表于2024年07月13日
题目中的交换操作以实现排序，本质就是冒泡排序的做法。因此，我们可以模拟冒泡排序的过程，如果在交换过程中发现需要交换的相邻两个元素的二进制数位1不同，那么就无法通过交换操作实现排序，返回False；否则，返回True。
上述的模拟冒泡排序做法的时间复杂度为O(n^2)，其实还有一种不用排序，且仅需一次遍历的做法。通过观察发现，某个元素能交换的位置范围是有限的，即该范围内所有的元素都具有相同的二进制数位1(即只能彼此交换，不能逾越到1计数不一样的元素那里)。我们可以将数组切分成若干个这样的区间，然后将每个区间的元素进行排序，最后观察整个数组是否有序即可。该做法还有个trick，而无需对区间进行排序：只要数组每个区间的最小值都大于其左边区间的最大值，那么就可以认为整个数组可以通过交换操作变为有序。
模拟冒泡排序的做法：
class Solution:
def canSortArray(self, nums: List[int]) -> bool:
for i in range(len(nums) - 1, 0, -1):
has_move = False
for j in range(i):
if nums[j] > nums[j + 1]:
if nums[j].bit_count() != nums[j + 1].bit_count():
return False
has_move = True
nums[j], nums[j + 1] = nums[j + 1], nums[j]
if not has_move:
break
return True使用区间的做法：
class Solution:
def canSortArray(self, nums: List[int]) -> bool:
last_grp_max = -1
i = 0
while i < len(nums):
grp_min = grp_max = nums[i]
set_bit_count = nums[i].bit_count()
j = i + 1
while j < len(nums):
if nums[j].bit_count() != set_bit_count:
break
grp_min = min(grp_min, nums[j])
grp_max = max(grp_max, nums[j])
j += 1
if last_grp_max != -1 and last_grp_max > grp_min:
# 如果当前区间的最小值小于上一个区间的最大值，说明无法实现整体有序
return False
last_grp_max = grp_max
i = j
return True