C++ 计算数组中具有严格较小和严格较大元素的元素的数量

严格较小的数字意味着该数字应比最小差异小1，并且类似地，严格较大的元素意味着该数字应比最小差异大1。 在这里，我们给出了大小为n的整数数组，并且我们必须返回数组中具有严格较小和严格较大元素的元素的数量。

让我们看看下面的示例以更好地理解问题。

示例示例

输入

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

输出结果

3

解释： 在上面的数组中：

数组[0]拥有array[3]作为严格大于的元素和array[1]作为严格小于的元素。

同样地，数组[1]拥有array[0]作为严格大于的元素和array[2]作为严格小于的元素。

同样地，数组[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)。