Easy

题目描述

给你一个整数数组 nums。

正整数的二进制反射定义为：将其二进制表示的数字顺序反转（忽略前导零），然后将结果的二进制数解释为十进制数。

根据每个元素的二进制反射值按升序对数组进行排序。如果两个不同的数字具有相同的二进制反射值，则较小的原数字应该排在前面。

返回排序后的数组。

示例 1：

输入: nums = [4,5,4]
输出: [4,4,5]
解释:
二进制反射值：
4 -> (二进制) 100 -> (反转) 001 -> 1
5 -> (二进制) 101 -> (反转) 101 -> 5
4 -> (二进制) 100 -> (反转) 001 -> 1

按反射值排序得到 [4, 4, 5]。

示例 2：

输入: nums = [3,6,5,8]
输出: [8,3,6,5]
解释:
二进制反射值：
3 -> (二进制) 11 -> (反转) 11 -> 3
6 -> (二进制) 110 -> (反转) 011 -> 3
5 -> (二进制) 101 -> (反转) 101 -> 5
8 -> (二进制) 1000 -> (反转) 0001 -> 1

按反射值排序得到 [8, 3, 6, 5]。
注意 3 和 6 具有相同的反射值，所以我们按原数值的升序排列它们。

提示：

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 10^9

解题思路

这道题需要我们根据数字的二进制反射值进行排序。解题思路如下：

步骤分析：

  1. 计算二进制反射值：对于每个数字，先将其转换为二进制字符串，然后反转这个字符串，最后转换回十进制数
  2. 自定义排序：使用自定义比较函数，首先按二进制反射值排序，如果反射值相同，则按原数值排序
  3. 处理细节：注意反转二进制字符串时要去除前导零

算法实现：

  • 创建辅助函数计算二进制反射值
  • 使用稳定排序算法，确保相同反射值的元素按原值排序
  • 时间复杂度主要取决于排序操作

优化考虑： 由于数据规模较小（最多100个元素），可以直接使用内置排序函数配合自定义比较器。对于二进制反射值的计算，可以通过位操作优化，但在此题规模下字符串操作已足够高效。

代码实现

class Solution {
public:
    int getBinaryReflection(int num) {
        string binary = "";
        while (num > 0) {
            binary += (num % 2) ? '1' : '0';
            num /= 2;
        }
        // binary is already reversed since we built it from right to left
        int reflection = 0;
        for (char c : binary) {
            reflection = reflection * 2 + (c - '0');
        }
        return reflection;
    }
    
    vector<int> sortByReflection(vector<int>& nums) {
        sort(nums.begin(), nums.end(), [this](int a, int b) {
            int reflectionA = getBinaryReflection(a);
            int reflectionB = getBinaryReflection(b);
            if (reflectionA == reflectionB) {
                return a < b;
            }
            return reflectionA < reflectionB;
        });
        return nums;
    }
};

class Solution:
    def sortByReflection(self, nums: List[int]) -> List[int]:
        def getBinaryReflection(num):
            binary_str = bin(num)[2:]  # Remove '0b' prefix
            reversed_binary = binary_str[::-1]
            return int(reversed_binary, 2)
        
        return sorted(nums, key=lambda x: (getBinaryReflection(x), x))

public class Solution {
    public int[] SortByReflection(int[] nums) {
        int GetBinaryReflection(int num) {
            string binary = Convert.ToString(num, 2);
            char[] binaryArray = binary.ToCharArray();
            Array.Reverse(binaryArray);
            string reversedBinary = new string(binaryArray);
            return Convert.ToInt32(reversedBinary, 2);
        }
        
        Array.Sort(nums, (a, b) => {
            int reflectionA = GetBinaryReflection(a);
            int reflectionB = GetBinaryReflection(b);
            if (reflectionA == reflectionB) {
                return a.CompareTo(b);
            }
            return reflectionA.CompareTo(reflectionB);
        });
        
        return nums;
    }
}

var sortByReflection = function(nums) {
    function getBinaryReflection(num) {
        return parseInt(num.toString(2).split('').reverse().join(''), 2);
    }
    
    return nums.sort((a, b) => {
        const reflectionA = getBinaryReflection(a);
        const reflectionB = getBinaryReflection(b);
        
        if (reflectionA === reflectionB) {
            return a - b;
        }
        return reflectionA - reflectionB;
    });
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n log n × k)，其中 n 是数组长度，k 是数字的平均二进制位数。排序需要 O(n log n)，每次比较需要计算二进制反射值 O(k)
空间复杂度O(k)，用于存储二进制字符串和递归调用栈