統計陣列中存在嚴格較小和嚴格較大元素的元素個數

---

一個數字嚴格小於另一個數字，意味著該數字至少比另一個數字小 1，類似地，嚴格大於另一個數字，意味著該數字至少比另一個數字大 1。這裡我們給定一個大小為 n 的整數陣列，我們需要返回陣列中存在嚴格較小和嚴格較大元素的元素個數。

讓我們看看下面的示例和解釋，以便更好地理解這個問題。

示例

輸入

N = 5
Array: [ 3, 2, 1, 4, 5 ]

輸出

3

解釋：在上面的陣列中

Array[0] 同時具有嚴格大於它的元素 array[3] 和嚴格小於它的元素 array[1]。

同樣，Array[1] 同時具有嚴格大於它的元素 array[0] 和嚴格小於它的元素 array[2]。

同樣，Array[3] 同時具有嚴格小於它的元素 array[2] 和嚴格大於它的元素 array[4]。

輸入

N = 3
Array: [ 2, 2, 6 ]

輸出

0

解釋：在上面的陣列中，沒有哪個索引同時具有嚴格大於和嚴格小於它的元素。

樸素方法

在這種方法中，我們使用巢狀 for 迴圈遍歷陣列，並檢查每個元素是否存在嚴格較小和嚴格較大元素。並根據條件儲存元素的計數，最後返回它。

讓我們看看下面的程式碼，以便更好地理解上述方法。

示例

統計陣列中存在嚴格較小和嚴格較大元素的元素個數的 C++ 程式碼

#include <bits/stdc++.h>
using namespace std;
//Create a function to count elements in the array 
int elementsCount(int N, int array[]) {
   int resCount = 0;   //Store the final ans
   //Create a bool element to check strictly smaller and greater elements
   bool strictlySmalleElement;
   bool strictlyGreaterElement;
   //Iterate the array using for loop
   for (int i = 0; i < N; i++) {
      strictlySmalleElement = false;
      strictlyGreaterElement = false;
      for (int j = 0; j < N; j++) {
         if (i != j) {
            // check for the smaller element
            if (array[j] < array[i])
               strictlySmalleElement = true;
            // check for the greater element
            else if (array[j] > array[i])
               strictlyGreaterElement = true;
         }
      }
       //count the element which has both strictly smaller and greater elements
      if (strictlySmalleElement && strictlyGreaterElement)
         resCount++; //Increase the count
   }
   return resCount;
}
int main() {
   int array[] = { 3, 2, 1, 4, 5 }; //Given array
   int N = sizeof(array) / sizeof(array[0]); //Getting the size of the array
   cout << "Count of Elements having strictly greater and smaller elements: ";
   cout<< elementsCount(N, array);
   return 0;
}

輸出

Count of Elements having strictly greater and smaller elements: 3

時間和空間複雜度

上面程式碼的時間複雜度為 O(N^2)，因為我們使用了巢狀 for 迴圈。其中 N 是字串的大小。

上面程式碼的空間複雜度為 O(1)，因為我們沒有使用任何額外的空間。

最佳化方法

在這種方法中，我們首先使用 for 迴圈找到給定陣列的最大和最小元素，然後再次遍歷給定陣列，並檢查每個元素是否小於最大元素且大於最小元素，如果是則增加計數並返回它。

讓我們看看下面的程式碼，以便更好地理解上述方法。

示例

統計陣列中存在嚴格較小和嚴格較大元素的元素個數的 C++ 程式碼。

#include <bits/stdc++.h>
using namespace std;
// Create a function to count elements in the array 
int elementsCount(int N, int array[]){
   // Create maxElement to store the maximum number and initialized it with INT_MIN
   int maxElement = INT_MIN;
   //Create minElement to store minimum number and initialized it with INT_MAX
   int minElement = INT_MAX;
   for( int i=0; i<N; i++ ){
      maxElement = max(maxElement, array[i]); // to get the maximum element
      minElement = min(minElement, array[i]); // to get the minimum element
   }
   int resCount = 0; // Store the final ans
   // Traverse the for loop to update resCount
   for (int i=0; i<N; i++) {
       // Check if current element is less than maximum element and greater than the minimum element 
      if (array[i] < maxElement && array[i] > minElement){
         resCount++; // Increase the count
      }
   }
   return resCount;
}
int main(){
   int array[] = { 3, 2, 1, 4, 5 }; //Given array
   int N = sizeof(array) / sizeof(array[0]); //Getting the size of the array
   cout << "Count of Elements having strictly greater and smaller elements: ";
   cout<< elementsCount(N, array);
   return 0;
}

輸出

Count of Elements having strictly greater and smaller elements: 3

時間和空間複雜度

上面程式碼的時間複雜度為 O(N)，因為我們只遍歷了給定陣列。其中 N 是字串的大小。

上面程式碼的空間複雜度為 O(1)，因為我們沒有使用任何額外的空間。

結論

在本教程中，我們實現了 C++ 程式來查詢統計陣列中存在嚴格較小和嚴格較大元素的元素個數。我們實現了兩種方法：樸素方法和最佳化方法。時間複雜度分別為 O(N^2) 和 O(N)。其中 N 是陣列的大小。兩種方法的空間複雜度均為 O(1)。