3769. 二进制反射排序

English Version

题目描述

给你一个整数数组 nums。

二进制反射 是对一个 正整数 的二进制表示按顺序反转（忽略前导零）后，将反转得到的二进制数转为十进制的结果。

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

返回排序后的数组。

示例 1：

示例 2：

提示：

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

解法

方法一：自定义排序

我们定义一个函数 $f(x)$ 来计算整数 $x$ 的二进制反射值。具体地，我们不断取出 $x$ 的最低位，并将其添加到结果 $y$ 的末尾，直到 $x$ 变为 $0$。

然后，我们对数组 $\textit{nums}$ 进行排序，排序的关键字为每个元素的二进制反射值和原始值的元组 $(f(x), x)$。这样可以确保当两个元素的二进制反射值相同时，较小的原始值会排在前面。

最后，我们返回排序后的数组。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 是数组 $\textit{nums}$ 的长度。

Python3

class Solution:
    def sortByReflection(self, nums: List[int]) -> List[int]:
        def f(x: int) -> int:
            y = 0
            while x:
                y = y << 1 | (x & 1)
                x >>= 1
            return y

        nums.sort(key=lambda x: (f(x), x))
        return nums

Java

class Solution {
    public int[] sortByReflection(int[] nums) {
        int n = nums.length;
        Integer[] a = new Integer[n];
        Arrays.setAll(a, i -> nums[i]);

        Arrays.sort(a, (u, v) -> {
            int fu = f(u);
            int fv = f(v);
            if (fu != fv) {
                return Integer.compare(fu, fv);
            }
            return Integer.compare(u, v);
        });

        for (int i = 0; i < n; i++) nums[i] = a[i];
        return nums;
    }

    private int f(int x) {
        int y = 0;
        while (x != 0) {
            y = (y << 1) | (x & 1);
            x >>= 1;
        }
        return y;
    }
}

C++

class Solution {
public:
    vector<int> sortByReflection(vector<int>& nums) {
        auto f = [](int x) {
            int y = 0;
            while (x) {
                y = (y << 1) | (x & 1);
                x >>= 1;
            }
            return y;
        };

        sort(nums.begin(), nums.end(), [&](int a, int b) {
            int fa = f(a);
            int fb = f(b);
            if (fa != fb) {
                return fa < fb;
            }
            return a < b;
        });

        return nums;
    }
};

Go

func sortByReflection(nums []int) []int {
	f := func(x int) int {
		y := 0
		for x != 0 {
			y = (y << 1) | (x & 1)
			x >>= 1
		}
		return y
	}

	sort.Slice(nums, func(i, j int) bool {
		fi := f(nums[i])
		fj := f(nums[j])
		if fi != fj {
			return fi < fj
		}
		return nums[i] < nums[j]
	})

	return nums
}

TypeScript

function sortByReflection(nums: number[]): number[] {
    const f = (x: number): number => {
        let y = 0;
        for (; x; x >>= 1) {
            y = (y << 1) | (x & 1);
        }
        return y;
    };

    nums.sort((a, b) => {
        const fa = f(a);
        const fb = f(b);
        if (fa !== fb) {
            return fa - fb;
        }
        return a - b;
    });

    return nums;
}