数组中至少是其他元素两倍的最大值

---

在本文中，我们将讨论不同的方法来指出数组中最大的元素，该元素至少是同一数组中所有其他元素的两倍。

问题陈述

给定一个包含 n 个不同元素的数组，我们必须找出给定数组 "nums" 中的最大元素，使其大于或等于该数组中所有其他元素的两倍。

换句话说，我们也可以说我们必须找出给定数组的所有其他元素是否都小于或等于数组中最大元素的一半。

现在让我们通过示例来理解问题陈述 -

示例 1

Input: nums = [ 2, 4, 1, 0 ]
Output: Index 1 contains the element in the array that is at least two times larger than any of the other elements.

解释

最大元素是 4，它至少是数组中所有其他元素的两倍。

示例 2

Input: nums = [ 5, 2, 9, 1 ]
Output: No such element found which is at least two times or greater than all the other elements.

解释

最大元素是 9，它至少是数组中所有其他元素的两倍。

可以有各种方法来解决这个问题，但让我们首先讨论蛮力法 -

方法 1

这是蛮力法，其中我们比较数组中每个元素与数组中其他每个元素，并检查某个元素是否大于或等于该数组中所有其他元素的两倍。如果某个元素既不大于也不等于该数组中所有其他元素的两倍，则代码移至下一个元素。如果找到有效元素，则代码记录其索引并停止查找其他元素。

示例

#include <iostream>
using namespace std;

int greatestelem ( int size, int nums[] ){
   int maxIndex = -1;
   for(int iterator =0; iterator < size; iterator++){
      bool flag = true;
      for(int temp =0; temp <size; temp++){
         if(iterator!=temp && nums[iterator]<2*nums[temp]){
            flag = false;
            break;
         }
      }
      if(flag){
         maxIndex = iterator;
         break;
      }
   }
   return maxIndex;
}
int main(){
   int nums[] = { 0, 1,  3, 6, 15 };
   int length = sizeof(nums) / sizeof( nums[0] ) ;
   int g= greatestelem( length , nums);
   if(g==-1){
      cout<< " No such element found which is greater than or equal to twice of all the other elements." << endl;
   } else {
      cout<< " The element in the array which is greater than or equal to twice of all the other elements is found at " << g << "th Index " << endl ;
   }
   return 0;
}

输出

The element in the array which is greater than or equal to twice of all the other elements is found at 4th Index

• 时间复杂度 - 此方法中使用的代码的时间复杂度为 O(m^2)，其中 m 是我们输入的数组的长度。

  由于我们使用了两个嵌套循环，每个循环都执行 n 次，因此内部循环的总迭代次数将是 n 乘以 n，导致 n^2 次迭代。

• 空间复杂度 - 因为我们只使用常量空间作为变量，所以此方法的空间复杂度为 O(1)。

方法 2

在此方法中，我们将只遍历数组两次，从而降低代码的时间复杂度。遍历数组两次的目的是 -

• 第一次遍历 - 找出给定数组中存在的最大元素。

• 第二次遍历 - 检查数组中最大的元素是否至少是同一数组中所有其他元素的两倍。

示例

现在让我们看看此特定方法的 C++ 代码 -

#include <bits/stdc++.h>
using namespace std;

int greatestelem(int nums[], int size){
   int IndMax = 0;
   for (int iterator = 0; iterator < size; ++iterator){
      if ( nums[iterator] > nums[IndMax]){
         IndMax = iterator;
      }
   }
   for (int iterator = 0; iterator < size; ++iterator){
      if ( IndMax != iterator && nums [IndMax] < 2 * nums[iterator]){
         return -1;
      }
   }
   return IndMax;
}
int main() {
   int nums[] = {3, 0, 2, 5, 15};
   int length = sizeof(nums) / sizeof( nums[0] ) ;
   int g= greatestelem(nums, length);
   if(g==-1)
      cout<< " No such element found which is greater than or equal to twice of all the other elements."<< endl;
   else 
      cout<< " The element in the array which is greater than or equal to twice of all the other elements is found at "<<g << "th Index " << endl;
   return 0;
}

输出

The element in the array which is greater than or equal to twice of all the other elements is found at 4th Index.

• 时间复杂度 - 此方法的时间复杂度为 O(length)，其中 "length" 是输入数组 "nums" 的大小。这样做的原因是代码使用两个嵌套循环分别遍历给定数组一次。在第一个循环中找到最大元素的时间复杂度为 O(n)，在第二个循环中检查最大元素是否大于或等于所有其他元素的两倍的时间复杂度为 O(n)。因此，总体时间复杂度为 O(n) + O(n) = O(n)。

• 空间复杂度 - 因为我们只使用常量空间作为变量，所以此方法的空间复杂度为 O(1)。