Java 中最大的数字至少是其他数字的两倍

给定一个具有唯一值的整数 数组，其中包含最大的 整数。检查数组中最大的数字是否至少是其他所有数字的两倍。如果是，则返回最大元素的索引；如果不是，则返回 -1。

示例 1

输入

int arr = [10,5,2,1]

输出

0

解释

最大的整数是 10。它至少是数组中其他所有数字的两倍。我们返回零，因为 10 的索引是 0。

示例 2

输入

int arr = [8,3,1,0]

输出

0

解释

最大的整数是八，它至少是每个其他数字的两倍。我们返回零，因为 8 的索引是 0。

示例 3

输入

int arr = [0,0,3,2]

输出

-1

解释

由于三至少不是二的两倍，因此即使它是最大的整数，我们也返回 -1。

方法：朴素方法

通过一次遍历，该代码有效地确定了数组中的最大数字，并确定它是否至少是每个其他数字的两倍（O(n) 时间复杂度）。为了确保尽可能少的比较，它使用两个变量跟踪最大和第二大项。逻辑保持简单，同时通过条件检查 maximum >= secondMax * 2 来保证正确性。通过避免不必要的排序和嵌套循环来提高性能。由于没有实现额外的数据结构，内存利用率保持不变（O(1) 空间复杂度）。由于其高效的架构，该程序可以处理大型数据集。

算法

步骤 1：将 MaxIndex、maximum 和 secondMax 设置为初始值。

步骤 2：迭代遍历数组。

步骤 2.1：如果当前元素大于 maximum，则将 secondMax 更新为 maximum。

步骤 2.1.1：将 maximum 更新为当前元素。

步骤 2.1.2：将 MaxIndex 更新为最近的索引。

步骤 2.2：另一方面，如果当前元素大于 secondMax。

步骤 2.2.1：将 secondMax 更新为当前元素。

步骤 3：检查条件：如果 maximum 大于或等于 second max 的两倍，则返回 MaxIndex；否则返回 -1。

实施

输出

 
0   

复杂度分析

上述算法的时间复杂度为 O(N)，其中 'N' 表示元素数量，空间复杂度为 O(1)。