思路分析
为便于叙述,下记:
- A: x的二进制
- B: x的二进制中非1的位置
由AND运算特点可知:
nums数组中的元素满足:如果 A 在某一位上为1,则nums中元素对应二进制在该位上也必须是1
换言之,从二进制码的视角看nums中元素,他们的二进制相当于以 A 为基础,在 B 上做了些调整
又因nums中元素互异且最小
- nums中最小值nums[0]就是x本身(将 B 中所有位置置于0)
- nums中最小值nums[n-1]就是将 B 中所有位置依次填上n-1的二进制的每一位
所以嗦,要计算返回的结果就是
先计算x的二进制码,再计算n-1的二进制码,最后将后者依次填进前者的0位上,得到的“杂交二进制”所对应的整数就是结果。
以下附上代码 & 笔者基于自身理解给出的注释:
class Solution {
public:long long minEnd(int n, int x) {//通过对x取反得到t,//通过计算t的lowbit来从低到高位遍历t的1位,即x的0位n-=1;int j=0;long long t = ~x; long long ans = x;//注意:n>>j 和 n>>j & 1的判断条件并不等价!while(n >> j){int lb = t & -t;//计算t的lowbitans |= (long long)((n>>j & 1) << j) * lb;//通过乘法运算巧妙实现了if语句的功能j++;t ^= lb;//更新t,将lb为1那位t值变成0}return ans;}
};
题解参考,膜拜灵神!
3133. 数组最后一个元素的最小值 - 力扣(LeetCode)
~希望对你有启发~