3011. Find if Array Can Be Sorted

⭐️⭐️⭐️

# 題目敘述

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.

# 解題思路

用簡單的 sort 演算法 Bubble Sort 進行，他的作法本身就是在與身邊的 array index value 做比較，進行交換，與題目要求相同，而接著我們只需要在檢查可以交換的兩個數字 bitcount 是否相同，若不同回傳 false。

• bitcount : 透過 n = n & (n - 1); 讓 n 去掉最前頭的數字 1，這樣我去掉過幾次，就知道有幾個數字 1。

# Solution

class Solution {

    public boolean canSortArray(int[] nums) {

        int n = nums.length;

        for(int i = 0; i < n - 1; i++) {

            for(int j = 0; j < n - 1 - i; j++) {

                if(nums[j] > nums[j+1]) {

                    if(bitcount(nums[j]) != bitcount(nums[j+1])) {

                        return false;

                    }

                    int temp = nums[j];

                    nums[j] = nums[j+1];

                    nums[j+1] = temp;

                }

            }

        }

        return true;

    }

    public int bitcount(int n) {

        int count = 0;

        while(n > 0) {

            count++;

            n = n & (n - 1);

        }

        return count;

    }

}