跳转至

3769. 二进制反射排序

题目描述

给你一个整数数组 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] <= 109

解法

方法一：自定义排序

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

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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;
}

评论