Question

3011. Find if Array Can Be Sorted

中文文档

Description

You are given a 0-indexed array of positive integers nums.

In one operation, you can swap any two adjacent elements if they have the same number of set bits. You are allowed to do this operation any number of times (including zero).

Return true _if you can sort the array, else return _false.

 

Example 1:

Input: nums = [8,4,2,30,15]
Output: true
Explanation: Let's look at the binary representation of every element. The numbers 2, 4, and 8 have one set bit each with binary representation "10", "100", and "1000" respectively. The numbers 15 and 30 have four set bits each with binary representation "1111" and "11110".
We can sort the array using 4 operations:
- Swap nums[0] with nums[1]. This operation is valid because 8 and 4 have one set bit each. The array becomes [4,8,2,30,15].
- Swap nums[1] with nums[2]. This operation is valid because 8 and 2 have one set bit each. The array becomes [4,2,8,30,15].
- Swap nums[0] with nums[1]. This operation is valid because 4 and 2 have one set bit each. The array becomes [2,4,8,30,15].
- Swap nums[3] with nums[4]. This operation is valid because 30 and 15 have four set bits each. The array becomes [2,4,8,15,30].
The array has become sorted, hence we return true.
Note that there may be other sequences of operations which also sort the array.

Example 2:

Input: nums = [1,2,3,4,5]
Output: true
Explanation: The array is already sorted, hence we return true.

Example 3:

Input: nums = [3,16,8,4,2]
Output: false
Explanation: It can be shown that it is not possible to sort the input array using any number of operations.

 

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 28

Solutions

Solution 1: Two Pointers

We can use two pointers to divide the array $nums$ into several subarrays, each with the same number of 1s in the binary representation of its elements. For each subarray, we only need to focus on its maximum and minimum values. If the minimum value is smaller than the maximum value of the previous subarray, then it is impossible to make the array sorted by swapping.

The time complexity is $O(n)$, where $n$ is the length of the array $nums$. The space complexity is $O(1)$.

class Solution:
  def canSortArray(self, nums: List[int]) -> bool:
    pre_mx = -inf
    i, n = 0, len(nums)
    while i < n:
      j = i + 1
      cnt = nums[i].bit_count()
      mi = mx = nums[i]
      while j < n and nums[j].bit_count() == cnt:
        mi = min(mi, nums[j])
        mx = max(mx, nums[j])
        j += 1
      if pre_mx > mi:
        return False
      pre_mx = mx
      i = j
    return True

class Solution {
  public boolean canSortArray(int[] nums) {
    int preMx = -300;
    int i = 0, n = nums.length;
    while (i < n) {
      int j = i + 1;
      int cnt = Integer.bitCount(nums[i]);
      int mi = nums[i], mx = nums[i];
      while (j < n && Integer.bitCount(nums[j]) == cnt) {
        mi = Math.min(mi, nums[j]);
        mx = Math.max(mx, nums[j]);
        j++;
      }
      if (preMx > mi) {
        return false;
      }
      preMx = mx;
      i = j;
    }
    return true;
  }
}

class Solution {
public:
  bool canSortArray(vector<int>& nums) {
    int preMx = -300;
    int i = 0, n = nums.size();
    while (i < n) {
      int j = i + 1;
      int cnt = __builtin_popcount(nums[i]);
      int mi = nums[i], mx = nums[i];
      while (j < n && __builtin_popcount(nums[j]) == cnt) {
        mi = min(mi, nums[j]);
        mx = max(mx, nums[j]);
        j++;
      }
      if (preMx > mi) {
        return false;
      }
      preMx = mx;
      i = j;
    }
    return true;
  }
};

func canSortArray(nums []int) bool {
  preMx := -300
  i, n := 0, len(nums)
  for i < n {
    j := i + 1
    cnt := bits.OnesCount(uint(nums[i]))
    mi, mx := nums[i], nums[i]
    for j < n && bits.OnesCount(uint(nums[j])) == cnt {
      mi = min(mi, nums[j])
      mx = max(mx, nums[j])
      j++
    }
    if preMx > mi {
      return false
    }
    preMx = mx
    i = j
  }
  return true
}

function canSortArray(nums: number[]): boolean {
  let preMx = -300;
  const n = nums.length;
  for (let i = 0; i < n; ) {
    let j = i + 1;
    const cnt = bitCount(nums[i]);
    let [mi, mx] = [nums[i], nums[i]];
    while (j < n && bitCount(nums[j]) === cnt) {
      mi = Math.min(mi, nums[j]);
      mx = Math.max(mx, nums[j]);
      j++;
    }
    if (preMx > mi) {
      return false;
    }
    preMx = mx;
    i = j;
  }
  return true;
}

function bitCount(i: number): number {
  i = i - ((i >>> 1) & 0x55555555);
  i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
  i = (i + (i >>> 4)) & 0x0f0f0f0f;
  i = i + (i >>> 8);
  i = i + (i >>> 16);
  return i & 0x3f;
}