What is the pattern behind the 'Keep Multiplying Found Values by Two' problem?

This problem follows an array scanning plus hash lookup pattern, where you iteratively check and update the value if found in the array.

How does the hash set help in this problem?

The hash set allows for O(1) time complexity for checking if a number exists in the array, improving the efficiency compared to direct array scanning.

Can this problem be solved without using a hash set?

Yes, but using a hash set significantly reduces the time complexity of searching for elements in the array.

What is the time complexity of the solution?

The time complexity depends on the number of iterations and the use of a hash set for O(1) lookups, making it O(n) in the worst case.

How can GhostInterview help me with this problem?

GhostInterview provides step-by-step guidance to solve this problem efficiently by focusing on the array scanning technique and optimizing with a hash set.

#2154

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

将找到的值乘以 2

给你一个整数数组 nums ，另给你一个整数 original ，这是需要在 nums 中搜索的第一个数字。接下来，你需要按下述步骤操作：如果在 nums 中找到 original ，将 original 乘以 2 ，得到新 original （即，令 original = 2 * origin…

数组哈希表排序模拟

题目描述

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

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

如果在 nums 中找到 original ，将 original 乘以 2 ，得到新 original（即，令 original = 2 * original）。
否则，停止这一过程。
只要能在数组中找到新 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 。

提示：

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

lightbulb

解题思路

方法一：哈希表

我们用一个哈希表 $\textit{s}$ 记录数组 $\textit{nums}$ 中的所有数字。

接下来，我们从 $\textit{original}$ 开始，如果 $\textit{original}$ 在 $\textit{s}$ 中，我们将 $\textit{original}$ 乘以 $2$ ，直到 $\textit{original}$ 不在 $\textit{s}$ 中，返回 $\textit{original}$ 。

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

1

2

3

4

5

6

7

class Solution:
    def findFinalValue(self, nums: List[int], original: int) -> int:
        s = set(nums)
        while original in s:
            original <<= 1
        return original

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate optimize array lookups using hash sets?
question_mark
Is the candidate comfortable with iterative problem-solving techniques?
question_mark
How well does the candidate handle the trade-off between time and space complexity?

warning

常见陷阱

外企场景

error
Not using a hash set to optimize the search operation.
error
Missing edge cases where the original value is never found in the array.
error
Failing to update the value properly after each multiplication step.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the array is sorted? Can you optimize the solution further?
arrow_right_alt
What if the problem involves multiple values to check and multiply?
arrow_right_alt
How would the solution change if we needed to track the number of iterations?

help

常见问题

外企场景

继续练习

#2357 使数组中所有元素都等于零 #2402 会议室 III #2593 标记所有元素后数组的分数