LeetCode 每日一题笔记

0. 前言

• 日期：2025.11.19
• 题目：2154.将找到的值乘以2
• 难度：简单
• 标签: 数组 哈希表

1. 题目理解

问题描述：
给你一个整数数组 nums ，另给你一个整数 original ，这是需要在 nums 中搜索的第一个数字。

接下来，你需要按下述步骤操作：

1. 如果在 nums 中找到 original ，将 original 乘以 2 ，得到新 original（即，令 original = 2 * original）。
2. 否则，停止这一过程。
3. 只要能在数组中找到新 original ，就对新 original 继续重复这一过程。 返回 original 的最终值。

示例：

示例 1： 输入：nums = [5,3,6,1,12], original = 3 输出：24 解释：

• 3 能在 nums 中找到。3 * 2 = 6 。
• 6 能在 nums 中找到。6 * 2 = 12 。
• 12 能在 nums 中找到。12 * 2 = 24 。
• 24 不能在 nums 中找到。因此，返回 24 。

示例 2： 输入：nums = [2,7,9], original = 4 输出：4 解释：

• 4 不能在 nums 中找到。因此，返回 4 。

2. 解题思路

核心观察

• 题目本质是寻找「original 及其 2 倍、4 倍、8 倍...」这个序列中，第一个不在 nums 数组中的元素。
• 序列的生成规则：从初始 original 开始，每次翻倍，直到数值超过 1000（题目隐含边界，因数组元素大概率不超过 1000，且翻倍后超过 1000 后无需继续判断）。

算法步骤

1. 保存初始值：用变量 old 保存初始的 original，避免后续翻倍操作修改原始判断基准。
2. 生成倍数序列：提前生成从初始 original 开始的所有 2 倍序列（original、2original、4original...），存入数组 arr，直到数值超过 1000 为止。
3. 标记存在的倍数：遍历 nums 数组，判断每个元素是否属于上述倍数序列：
   • 若元素是初始 original（nums[j] == old），标记序列中第一个元素（arr[0]）为 0。
   • 若元素是初始 original 的倍数（nums[j]%2==0 && nums[j]%old==0），遍历倍数序列 arr，找到对应的元素并标记为 0（表示该倍数在 nums 中存在）。
4. 寻找最终结果：遍历倍数序列 arr，返回第一个未被标记（值不为 0）的元素；若所有倍数都被标记，则返回最后一个倍数的 2 倍（即循环结束后 original 的值）。

3. 代码实现

import java.util.Arrays;

class lc3600_lc3699.lc3660.Solution {
    public static int findFinalValue(int[] nums, int original) {
        int old = original;
        Arrays.sort(nums);
        //声明一个一维数组
        int[] arr = new int[99];
        int i = 0;
        while (original <= 1000) {
            arr[i] = original;
            original *= 2;
            i++;
        }
        //遍历nums数组
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] == old) {
                arr[0] = 0;
            }
            if (nums[j] % 2 == 0 && nums[j] % old == 0) {
                //遍历arr数组
                for (int k = 0; k < arr.length; k++) {
                    if (nums[j] == arr[k]) {
                        arr[k] = 0;
                    }
                }
            }
        }
        //遍历arr
        for (int j = 0; j < arr.length; j++) {
            if (arr[j] != 0) {
                return arr[j];
            }
        }
        return original;
    }
}

4. 代码优化说明

现有代码的可优化点

1. 判断条件冗余：nums[j]%2==0 && nums[j]%old==0 存在逻辑漏洞（如初始 original=3 时，nums[j]=3 是有效倍数，但 3%2≠0 会被过滤），可直接通过「判断 nums[j] 是否在倍数序列 arr 中」替代。
2. 查询效率较低：遍历 nums 时，嵌套遍历 arr 查找匹配元素（时间复杂度 O(n*m)，n 为 nums 长度，m 为 arr 长度），可通过排序+二分查找或哈希表优化。
3. 数组长度固定：arr 长度固定为 99 存在浪费（实际倍数序列长度不超过 10，因 1*2^10=1024>1000），可动态计算长度或使用 List 存储。

优化方案（推荐哈希表版）

import java.util.HashSet;
import java.util.Set;

class lc3600_lc3699.lc3660.Solution {
    public int findFinalValue(int[] nums, int original) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        while (numSet.contains(original)) {
            original *= 2;
        }
        return original;
    }
}

• 优化逻辑：用 HashSet 存储 nums 元素，O(1) 时间复杂度查询 original 是否存在，循环翻倍直到不存在为止，代码更简洁、效率更高（时间复杂度 O(n)）。

5. 复杂度分析

原代码复杂度

• 时间复杂度：O(n*m + n log n)
  • O(n log n)：对 nums 数组排序的时间。
  • O(n*m)：遍历 nums 数组（O(n)），每个元素嵌套遍历 arr 数组（O(m)），m 为 arr 数组长度（固定 99）。
• 空间复杂度：O(m)：存储倍数序列的 arr 数组（长度 99）。

优化后（哈希表版）复杂度

• 时间复杂度：O(n)
  • O(n)：将 nums 元素存入 HashSet 的时间。
  • 循环翻倍的次数最多为 log2(1000)≈10 次，可忽略，整体时间复杂度由 n 决定。
• 空间复杂度：O(n)：HashSet 存储 nums 元素的空间。

6. 总结

题目核心

本题的核心是「倍数序列的存在性判断」，关键在于高效验证每个倍数是否在数组中，避免冗余计算。

原代码思路总结

原代码通过「提前生成倍数序列+标记存在元素」的思路解题，逻辑可行但存在效率和严谨性问题，适合理解基础的数组操作和序列生成逻辑。

• 此类题目常考察「哈希表的应用」「序列生成逻辑」「时间复杂度优化」，需掌握哈希表的基本操作（增、查）。
• 遇到「存在性判断」「去重」「快速查询」场景，优先考虑哈希表（HashSet/HashMap）。
• 需注意边界情况：如 original 初始值不在 nums 中、所有倍数都在 nums 中等，确保代码覆盖所有场景。