Java 中查找最接近目标的神秘函数的值

给定一个整数数组 (arr) 和一个整数 target，我们需要找到通过对 arr 的非空子数组执行按位 AND 操作可以获得的、最接近 target 的值。任务是返回计算出的 AND 值与 target 之间的最小绝对差。

示例 1

输入

arr = {9, 12, 3, 7, 15}

target = 5

输出：最接近的值：2

解释：可能的 AND 值：{9, 8, 0, 0, 0}。最接近 5 的值是 2（来自 abs(0 - 5) = 2）。

示例 2

输入

arr = {8, 6, 2}

target = 4

输出：最接近的值：2

解释：计算出的 AND 值为 {8, 0, 0}，最接近 4 的值是 2，来自 abs(2 - 4) = 2。

方法 1：暴力枚举法

该方法遍历给定数组的所有可能子数组并计算它们的按位 AND 值。然后通过计算绝对差值找到最接近给定目标的那个值。

算法

步骤 1：将 closest 初始化为 Integer.MAX_VALUE。

步骤 2：遍历数组中的每个索引 i

步骤 2.1：以 arr[i] 作为初始 AND 值。

步骤 2.2：遍历所有后续索引 j

步骤 2.2.1：计算从 i 到 j 的子数组的按位 AND。

步骤 2.2.2：如果与目标的绝对差值更小，则更新 closest。

步骤 2.2.3：如果 AND 值小于或等于 target，则提前停止，因为进一步的 AND 操作不会增加它。

步骤 3：返回找到的最接近值。

让我们在 Java 程序中实现上述步骤。

输出

 
Closest Value: 2   

复杂度

时间复杂度：程序的 O(n^2)，其中 n 是数组的大小。这是因为我们为每个子数组计算 AND 操作。

空间复杂度：程序的 O(1)。因为我们只使用几个整数变量。

方法 2：使用 Set

该方法通过对非空子数组执行按位 AND 操作来搜索最接近目标的值。而不是遍历所有可能的子数组（这效率低下），我们使用一个 Set 来在每一步维护唯一的 AND 值。

算法

步骤 1：初始化一个空的 Set 来存储前几次迭代的可能 AND 结果。

步骤 2：遍历数组

步骤 2.1：创建一个新的 Set（newSet），其中存储

步骤 2.1.1：当前元素。

步骤 2.1.2：当前元素与 andSet 中每个值的 AND 结果。

步骤 2.2：将 newSet 更新为 andSet，用于下一次迭代。

步骤 2.3：计算与目标的绝对差值，并更新最接近的结果。

步骤 3：返回找到的最接近值。

输出

 
Closest Value: 2   

复杂度

时间复杂度：程序的 O(n log m)。这是因为每个元素最多会与 log M 个不同的值进行 AND 操作，其中 M 是可能的 AND 结果的最大值。

空间复杂度：程序的 O(log m)。因为 Set 每轮最多存储 log M 个不同的值。

方法 3：动态规划

该方法通过维护跨子数组的按位 AND 值的动态列表来查找最接近给定目标的值。

算法

步骤 1：维护一个列表 (andList) 来存储前一个元素的活动 AND 值。

步骤 2：对于数组中的每个元素

步骤 2.1：创建一个新列表 (newList)，其中第一个元素是当前数字。

步骤 2.2：计算 num 与前一个 AND 结果之间的 AND 操作。

步骤 2.3：只存储唯一的 AND 值以避免冗余。

步骤 2.4：通过检查与目标的绝对差值来更新 closest。

步骤 3：该过程会持续到所有元素都被处理，从而确保有效地搜索最接近的值。

输出

 
Closest Value: 2   

复杂度

时间复杂度：程序的 O(n log m)。这是因为每个元素都被处理一次，并且一个数字最多存在 log M 个唯一的 AND 值。

空间复杂度：程序的 O(log m)。因为 andList 的大小最多保持为 log M，其中 M 是可能的 AND 结果的最大值。