LeetCode-1356-Sort-Integers-By-Number-Of-1-Bits

🧠 Summary of Thoughts

1. Precompute bit counts using a HashMap
2. Convert int[] to Integer[], since Arrays.sort() with a custom Comparator does NOT work on primitive int[]
3. Sort using a custom Comparator
4. Copy back to int[]

Learned:

1. Custom sort:
   Arrays.sort(nums, new Comparator<Integer>() { ... });

2. Lambda Structure:

   (a, b) -> {
       //...
   }
   
   // it is equvalent to:
   
   
   public int compare(Integer a, Integer b) {
       //...
   }  

   • Example:

     1. tradition method:

        Arrays.sort(nums, new Comparator<Integer>() {
        
            @Override
            public int compare(Integer a, Integer b) {
        
                int bitA = arrays.get(a);
                int bitB = arrays.get(b);
        
                if (bitA != bitB) {
                    return bitA - bitB;
                }
        
                return a - b;
            }
        });

     2. Lambda:

        Arrays.sort(nums, (a, b) -> {
            int bitA = arrays.get(a);
            int bitB = arrays.get(b);
        
            if (bitA != bitB) {
                return bitA - bitB;
            }
        
            return a - b;
        });

❗ Easily wrong point

• We need to copy each arr element into a temporary variable so as to protect the original values!!!

✅ Code（Java）

1.

class Solution {
    public int[] sortByBits(int[] arr) {
        // x = 2^0 + 2^1 + 2^2 + 2^3 + ... + 2^n
        Map<Integer, Integer> arrays = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            int num = arr[i];
            int temp = num;
            int count = 0;
            while (temp != 0) {
                int module = temp % 2;
                if (module == 1) {
                    count++;
                }
                temp /= 2;
            }
            arrays.put(num, count);
        }
        // boxing
        Integer[] nums = new Integer[arr.length];
        for (int i = 0; i < arr.length; i++) {
            nums[i] = arr[i];
        }
        Arrays.sort(nums, new Comparator<Integer>() {
            @Override
            public int compare (Integer a, Integer b) {
                int bitA = arrays.get(a);
                int bitB = arrays.get(b);
                if (bitA != bitB) {
                    return bitA - bitB;
                }
                return a - b;
            }
        });
        for (int i = 0; i < arr.length; i++) {
            arr[i] = nums[i];
        }
        return arr;
    }
}

2. optimal solution

import java.util.*;

class Solution {
    public int[] sortByBits(int[] arr) {
        
        Integer[] nums = new Integer[arr.length];
        for (int i = 0; i < arr.length; i++) {
            nums[i] = arr[i];
        }

        Arrays.sort(nums, (a, b) -> {
            int bitA = Integer.bitCount(a);
            int bitB = Integer.bitCount(b);
            
            if (bitA != bitB) {
                return bitA - bitB;
            }
            return a - b;
        });

        for (int i = 0; i < arr.length; i++) {
            arr[i] = nums[i];
        }

        return arr;
    }
}