使用 C++ 查找最小值和最大值相同的子数组的数量
在本文中，我们将使用 C++ 解决查找最大和最小元素相同的子数组的数量的问题。以下是问题 − 的示例
输入:array = { 2, 3, 6, 6, 2, 4, 4, 4 }
输出:12
说明:{2}、{3}、{6}、{6}、{2}、{4}、{4}、{4}、{6,6}、{4,4}、{4,4} 和 { 4,4,4 } 是可以形成的具有最大和最小元素相同的子数组。
输入:数组 = { 3,3,1,5,1,2,2 }
输出:9
解释:{3}、{3}、{1}、{5}、{1}、{2}、{2}、{3,3} 和 {2,2} 是可以形成的子数组，其中最小值和最大值相同。
寻找解决方案的方法
查看示例，我们可以说可以形成的子数组的最小数量相同，最小值和最大值元素等于数组的大小。如果有相同的连续数字，子数组的数量可能会更多。
因此，我们可以采用遍历每个元素并检查其连续数字是否相同的方法，如果连续数字相同，则增加计数，如果发现不同的数字，则中断内循环。
每次内循环结束或中断时，结果变量都会增加结果变量，最后显示结果变量的结果。
示例
#include <bits/stdc++.h>
using namespace std;
int main(){
int a[ ] = { 2, 4, 5, 3, 3, 3 };
int n = sizeof(a) / sizeof(a[0]);
int result = n, count =0;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if(a[i]==a[j])
count++;
else
break;
}
result+=count;
count =0;
}
cout << "具有最小和最大元素相同的子数组的数量:<< result;
return 0;
}
输出
具有最小和最大元素相同的子数组的数量:9 时间复杂度 = O(n2)。
上述代码的解释
在此代码中，我们采用变量 n 来存储数组的大小，result = n，因为可以形成最小 n 个子数组并进行计数以保持相同数字的数量。
外循环用于处理数组中的每个元素。内循环用于查找索引元素后有多少个连续的数字相同，并在每次内循环结束时使用计数变量增加结果变量。最后显示存储在结果变量中的输出。
高效方法
在这种方法中，我们遍历每个元素，对于每个元素，我们都在搜索有多少个连续相同的数字。对于找到的每个相同的数字，我们都会增加计数变量，当找到不同的数字时，在计数的帮助下，我们使用公式"n = n*(n+1)/2"查找可以形成多少个子数组，并使用此公式的答案增加结果变量。
示例
#include <bits/stdc++.h>
using namespace std;
int main(){
int a[] = { 2, 4, 5, 3, 3, 3 };
int n = sizeof(a) / sizeof(a[0]);
int result = 0;
int count =1,temp=a[0];
for (int i = 1; i < n; i++) {
if (temp==a[i]){
count++;
}
else{
temp=a[i];
result = result + (count*(count+1)/2);
count=1;
}
}
result = result + (count*(count+1)/2);
cout << "具有最小和最大元素相同的子数组的数量:" << result;
return 0;
}
输出
具有最小和最大元素相同的子数组的数量:9 时间复杂度:O(n)
上述代码的解释
在此代码中，我们将数组的第 0 个索引存储在临时变量中，并从索引 1 开始循环。我们检查临时变量是否等于当前索引处的元素，并对找到的相同数字将计数加 1。如果临时变量不等于索引元素，则我们找到可以从相同数字的计数中组成的子数组的组合，并将结果存储在结果变量中。我们将临时值更改为当前索引，将计数重置为 1。最后，我们显示存储在结果变量中的答案。
结论
在本文中，我们解决了一个问题，即查找最小和最大元素相同的子数组的数量。我们还学习了这个问题的 C++ 程序以及我们解决这个问题的完整方法(正常和高效)。我们可以用其他语言(如 C、java、python 和其他语言)编写相同的程序。希望您觉得这篇文章有用。
