计算数组中存在严格较小和严格较大元素的元素数量
数字严格较小意味着该数字应小于 ,最小差为 1 ,同样,严格较大意味着该数字应大于 ,最小差为 1 。这里我们给出了一个大小为 n 的整数数组,我们必须返回数组中存在严格较小和严格较大元素的元素数量。
让我们看下面的示例和解释,以更好地理解问题。
示例
输入
N = 5 数组:[ 3, 2, 1, 4, 5 ]
输出
3
解释:在上述数组中:
Array[0] 的两个元素 array[3] 都严格大于 array[3],而 array[1] 都严格小于 array[1]。
同样,Array[1] 的两个元素 array[0] 都严格大于 array[2],而 array[2] 都严格小于 array[2]。
同样,Array[3] 的两个元素 array[2] 都严格小于 array[4],而 array[4] 都严格大于 array[4]。
输入
N = 3 数组:[ 2, 2, 6 ]
输出
0
解释:在上述数组中,没有索引同时具有元素严格大于和严格小于。
简单方法
在这种方法中,我们使用嵌套的 for 循环遍历数组,并检查每个元素是否存在严格小于和严格大于的元素。并根据条件存储元素数量,最后返回它。
让我们看下面的代码以更好地理解上述方法。
示例
用于计数数组中存在严格小于和严格大于元素的元素的 C++ 代码
#include <bits/stdc++.h> using namespace std; //创建一个函数来计算数组中的元素 int elementsCount(int N, int array[]) { int resCount = 0; //存储最终答案 //创建一个 bool 元素来严格检查较小和较大的元素 bool strictlySmalleElement; bool strictlyGreaterElement; //使用 for 循环迭代数组 for (int i = 0; i < N; i++) { strictlySmalleElement = false; strictlyGreaterElement = false; for (int j = 0; j < N; j++) { if (i != j) { // 检查较小的元素 if (array[j] < array[i]) strictlySmalleElement = true; // 检查较大的元素 else if (array[j] > array[i]) strictlyGreaterElement = true; } } //计算同时具有严格小于和大于元素的元素 if (strictlySmalleElement && strictlyGreaterElement) resCount++; //增加计数 } return resCount; } int main() { int array[] = { 3, 2, 1, 4, 5 }; //给定数组 int N = sizeof(array) / sizeof(array[0]); //获取数组的大小 cout << "具有严格大于和小于元素的元素数量:"; cout<< elementsCount(N, array); return 0; }
输出
具有严格大于和小于元素的元素数量:3
时间和空间复杂度
由于我们使用了嵌套 for 循环,因此上述代码的时间复杂度为 O(N^2)。其中 N 是字符串的大小。
上述代码的空间复杂度为 O(1),因为我们没有使用任何额外空间。
优化方法
在此方法中,我们首先使用 for 循环找到给定数组的最大和最小元素,然后再次遍历给定数组并检查每个元素是否小于最大元素并大于最小元素,然后增加计数并返回它。
让我们看下面的代码以更好地理解上述方法。
示例
数组中 Count 元素的 C++ 代码具有严格较小和严格较大的元素。
#include <bits/stdc++.h> using namespace std; // 创建一个函数来计算数组中的元素数量 int elementsCount(int N, int array[]){ // 创建 maxElement 来存储最大数量并用 INT_MIN 初始化 int maxElement = INT_MIN; // 创建 minElement 来存储最小数量并用 INT_MAX 初始化 int minElement = INT_MAX; for( int i=0; i<N; i++ ){ maxElement = max(maxElement, array[i]); // 获取最大元素 minElement = min(minElement, array[i]); // 获取最小元素 } int resCount = 0; // 存储最终答案 // 遍历 for 循环以更新 resCount for (int i=0; i<N; i++) { // 检查当前元素是否小于最大元素且大于最小元素 if (array[i] < maxElement && array[i] > minElement){ resCount++; // 增加计数 } } return resCount; } int main(){ int array[] = { 3, 2, 1, 4, 5 }; //给定数组 int N = sizeof(array) / sizeof(array[0]); //获取数组的大小 cout << "具有严格大于和小于元素的元素数量:"; cout<< elementsCount(N, array); return 0; }
输出
具有严格大于和小于元素的元素数量:3
时间和空间复杂度
上述代码的时间复杂度为 O(N),因为我们只遍历给定的数组。其中 N 是字符串的大小。
上述代码的空间复杂度为 O(1),因为我们没有使用任何额外空间。
结论
在本教程中,我们实现了一个 C++ 程序来查找数组中存在严格较小和严格较大元素的 Count 个元素。我们实现了两种方法:简单方法和优化方法。时间复杂度分别为 O(N^2) 和 O(N)。其中 N 是数组的大小。两种方法的空间复杂度均为 O(1)。