题目链接：2154. 将找到的值乘以 2（简单）

算法原理：

👉对应LeetCode题解

解法一：排序+枚举

6ms击败31.18%

时间复杂度：O(nlogn)

排序之后就有了递增的单调性，original变成2倍之后只能增加（题目说了original>=1），枚举nums每个元素的时候不需要往回看

解法二：哈希表

4ms击败61.29%

时间复杂度O(N)

直接模拟，将所有元素全扔Set里，反正也不需要用到重复的数据嘛，只要有original就把original变2倍

解法三：位运算

1ms击败92.83%

时间复杂度O(N)

①问题本质转化
最小（第一个）的非负整数 k，使得 original × 2ᵏ 不在数组里，最终答案就是 original × 2ᵏ
②只关心一类数
数组里只有形如 original × 2ᵗ（t 为自然数）的数有用，其余数直接忽略
③用一个整数标记是否存在
用 mask 的二进制位记录：
第 t 位 = 1 → original × 2ᵗ 在数组里存在
第 t 位 = 0 → 不存在
④快速筛选有效数
对每个数 x：
先判断：x 能被 original 整除
再判断：x/original 是 2 的幂（k & (k-1) == 0）
满足就把对应位标记为 1
⑤按位取反找缺失位
~mask 后：
原本存在的位（1）→ 变 0
原本缺失的位（0）→ 变 1
⑥lowbit 找“第一个缺失”
mask & -mask 能取出最右边的 1，对应最小的缺失 2ᵏ，乘回 original 就是答案

Java代码：

class Solution {
    //解法一：排序+枚举
    public int findFinalValue(int[] nums, int original) {
        Arrays.sort(nums);
        for(int x:nums)
            if(x==original)
                original*=2;
        return original;
    }
}

class Solution {
    //解法二：哈希表
    public int findFinalValue(int[] nums, int original) {
        Set<Integer> hash=new HashSet<>();
        for(int x:nums) hash.add(x);
        while(hash.contains(original)) original*=2;
        return original;
    }
}

class Solution {
    //解法三：位运算
    public int findFinalValue(int[] nums, int original) {
        //mask第k位为1，表示original×2ᵏ在数组中存在
        int mask=0;
        for(int x:nums){
            //我们只关心x=original×2ᵏ这种形式的数
            int k=x/original;
            //满足以下两个条件
            //①x是original的整数倍→能被整除
            //②k是2的幂
            //k&(k-1)：判断是不是2的幂的经典方法
            if(x%original==0&&(k&(k-1))==0) 
                //把mask里第k位设为1，表示original×2ᵏ存在
                mask|=k;
        }
        //我们要找第一个不满足的：需要按位取反，取出最右侧的1，即为第一个不满足的
        mask=~mask;
        return original*(mask&-mask);
    }
}