陣列中至少是其他元素兩倍的最大值

---

在本文中，我們將討論不同的方法來指出陣列中最大的元素，該元素至少是同一陣列中所有其他元素的兩倍。

問題陳述

給定一個包含 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)。