2154.将找到的值乘以 2#

题目#

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

思路#

最简单思路：存入map，能O1判断元素是否存在，这样时间复杂度是On，空间On

升级思路：事先判断与original有关再存入，筛选掉无关数据，可以节省空间和map查询效率。

代码#

一般思路：

func findFinalValue(nums []int, original int) int {
	// 直到不能找到
	m := make(map[int]bool)
	for _, num := range nums {
		m[num] = true
	}
	for {
		if m[original] {
			original *= 2
		} else {
			return original
		}
	}
	return original
}

提升：

func findFinalValue(nums []int, original int) int {
	// 直到不能找到
	m := make(map[int]bool)
	// 只存和original有关的
	for _, num := range nums {
		if num%original == 0 { // 先确保能整除
			n := num / original
			if n != 0 && n&(n-1) == 0 { // n是2的幂（且非0）
				m[num] = true
			}
		}
	}

	for m[original] {
		original *= 2
	}
	return original
}