2154. 将找到的值乘以 2
2154. 将找到的值乘以 2
🟢 🔖 数组
哈希表
排序
模拟
🔗 力扣
LeetCode
题目
You are given an array of integers nums
. You are also given an integer original
which is the first number that needs to be searched for in nums
.
You then do the following steps:
- If
original
is found innums
, multiply it by two (i.e., setoriginal = 2 * original
). - Otherwise, stop the process.
- Repeat this process with the new number as long as you keep finding the number.
Return the final value of original
.
Example 1:
Input: nums = [5,3,6,1,12], original = 3
Output: 24
Explanation:
- 3 is found in nums. 3 is multiplied by 2 to obtain 6.
- 6 is found in nums. 6 is multiplied by 2 to obtain 12.
- 12 is found in nums. 12 is multiplied by 2 to obtain 24.
- 24 is not found in nums. Thus, 24 is returned.
Example 2:
Input: nums = [2,7,9], original = 4
Output: 4
Explanation:
- 4 is not found in nums. Thus, 4 is returned.
Constraints:
1 <= nums.length <= 1000
1 <= nums[i], original <= 1000
题目大意
给你一个整数数组 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
解题思路
使用 Set 优化查询效率:
- 由于需要频繁判断某个值是否存在于数组中,使用哈希集合
Set
存储nums
中的元素。 - 这样可以将每次查询的时间复杂度降为
O(1)
。
- 由于需要频繁判断某个值是否存在于数组中,使用哈希集合
循环处理:
- 在集合中检查当前的
original
是否存在。 - 如果存在,将
original
乘以2
并继续循环。 - 如果不存在,跳出循环并返回当前的
original
值。
- 在集合中检查当前的
复杂度分析
时间复杂度:
O(n)
- 将数组转换为集合的时间复杂度是
O(n)
。 - 循环过程中,每次查询
set.has(original)
的时间复杂度是O(1)
,最多查询log(max / original)
次,其中max
是数组中的最大值。 - 因此,总时间复杂度为
O(n)
。
- 将数组转换为集合的时间复杂度是
空间复杂度:
O(n)
,使用了一个哈希集合存储数组元素。
代码
/**
* @param {number[]} nums
* @param {number} original
* @return {number}
*/
var findFinalValue = function (nums, original) {
let set = new Set(nums); // 将数组转换为集合
while (set.has(original)) {
// 如果集合中存在当前 original
original *= 2; // 乘以 2
}
return original; // 返回最终值
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
747 | 至少是其他数字两倍的最大数 | [✓] | 数组 排序 | 🟢 | 🀄️ 🔗 |
1346 | 检查整数及其两倍数是否存在 | [✓] | 数组 哈希表 双指针 2+ | 🟢 | 🀄️ 🔗 |