将找到的值乘以 2

标签: 数组 哈希表 排序 模拟

难度: Easy

给你一个整数数组 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 。

提示：

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

Submission

运行时间: 26 ms

内存: 16.1 MB

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

Explain

此题解采用的是简单的迭代思路。它从给定的 original 值开始，不断地检查该值是否在 nums 数组中。如果在，就将该值乘以 2，然后继续检查。这个过程一直持续到 original 不再出现在 nums 中为止。最终返回的 original 就是经过多次翻倍后的结果。

时间复杂度: O(nlog2(max(nums)))

空间复杂度: O(1)

class Solution:
    def findFinalValue(self, nums: List[int], original: int) -> int:
        while original in nums:  # 检查 original 是否在 nums 中
            original *= 2  # 如果在，则将 original 翻倍
        return original  # 返回最终的 original 值

Explore

迭代方法简单且直接，适用于无须额外数据结构的情况下求解问题。然而，它在效率上并不总是最优。例如，如果将 nums 数组转换为哈希集合，可以将 `in` 操作的时间复杂度从 O(n) 降低到平均 O(1)，从而提高整个算法的效率。此外，如果知道数字的范围有限，可以使用数组或位向量来进一步优化查找操作。

如果 `nums` 数组非常大，每次 `in` 操作都需要遍历整个数组，这会导致性能显著下降，特别是在 `original` 需要多次翻倍才能找到不在数组中的值时。如果 `original` 的值非常小，它可能需要多次迭代才能达到一个不再 `nums` 中的值，每次迭代都可能涉及到整个数组的遍历，从而导致性能问题。

在 Python 中，`in` 操作对于列表来说是通过线性搜索实现的，其时间复杂度为 O(n)，这意味着每次检查都需要遍历整个数组。这种方式在数据量较小时表现尚可，但随着数据量增加，性能会显著下降。因此，这种检查方式并不能保证最优的性能，尤其是在处理大规模数据时。

在当前的算法实现中，`nums` 数组中的重复元素不会对结果产生影响，因为我们只关心某个值是否存在于数组中，而不关心它出现的次数。然而，重复元素会增加每次 `in` 操作的处理时间，因为即使在找到匹配项后，搜索仍将继续到数组末尾。因此，重复元素会降低算法的效率。