Easy

题目描述

给你一个整数数组 nums。同时给你一个整数 original，这是第一个需要在 nums 中搜索的数字。

然后你需要按以下步骤操作：

  1. 如果在 nums 中找到 original，将它乘以 2（即，设置 original = 2 * original）。
  2. 否则，停止这个过程。
  3. 用新的数字重复这个过程，只要你能持续找到这个数字。

返回 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。

约束条件：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i], original <= 1000

解题思路

这道题的核心思路是模拟题目描述的过程：不断查找当前的 original 值是否存在于数组中，如果存在就将其乘以2，直到找不到为止。

解法分析：

  1. 暴力模拟：每次都遍历整个数组查找 original，时间复杂度为 O(n²)。

  2. 哈希表优化（推荐）：将数组元素预先存储在哈希集合中，这样每次查找的时间复杂度降为 O(1)，整体时间复杂度为 O(n)。

算法步骤：

  1. 将 nums 数组的所有元素加入哈希集合
  2. 循环检查当前 original 是否在集合中：
    • 如果存在，将 original 乘以 2
    • 如果不存在，跳出循环
  3. 返回最终的 original 值

由于题目约束条件中数字都不超过1000，且我们每次都是乘以2，所以最多只需要循环10次左右就能得到结果，算法效率很高。

代码实现

class Solution {
public:
    int findFinalValue(vector<int>& nums, int original) {
        unordered_set<int> numSet(nums.begin(), nums.end());
        
        while (numSet.count(original)) {
            original *= 2;
        }
        
        return original;
    }
};

class Solution:
    def findFinalValue(self, nums: List[int], original: int) -> int:
        num_set = set(nums)
        
        while original in num_set:
            original *= 2
        
        return original

public class Solution {
    public int FindFinalValue(int[] nums, int original) {
        HashSet<int> numSet = new HashSet<int>(nums);
        
        while (numSet.Contains(original)) {
            original *= 2;
        }
        
        return original;
    }
}

/**
 * @param {number[]} nums
 * @param {number} original
 * @return {number}
 */
var findFinalValue = function(nums, original) {
    const numSet = new Set(nums);
    
    while (numSet.has(original)) {
        original *= 2;
    }
    
    return original;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型推荐解法（哈希表）暴力解法
时间复杂度O(n)O(n²)
空间复杂度O(n)O(1)

说明：

  • 时间复杂度：O(n) - 构建哈希集合需要 O(n)，while 循环最多执行约 log(1000) ≈ 10 次
  • 空间复杂度：O(n) - 哈希集合存储所有数组元素

相关题目