发表于 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

• LC 题目链接