统计数组中存在严格较小和严格较大元素的元素个数

---

一个数字严格小于另一个数字，意味着该数字至少比另一个数字小 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)。