数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学使用 C++ 查找最小值和最大值相同的子数组个数
在本文中，我们将解决使用 C++ 查找最大和最小元素相同的子数组个数的问题。以下是这个问题的示例：
Input : array = { 2, 3, 6, 6, 2, 4, 4, 4 }
Output : 12
Explanation : {2}, {3}, {6}, {6}, {2}, {4}, {4}, {4}, {6,6}, {4,4}, {4,4} and { 4,4,4 } are the subarrays which can be formed with maximum and minimum element same.
Input : array = { 3,3,1,5,1,2,2 }
Output : 9
Explanation : {3}, {3}, {1}, {5}, {1}, {2}, {2}, {3,3} and {2,2} are the subarrays which can be formed with minimum and maximum are the same.解决方案方法
观察示例，我们可以说，可以形成的最小子数组个数等于数组的大小，其最小和最大元素相同。如果存在连续相同的数字，则子数组个数可能会更多。
因此，我们可以采用一种方法，遍历每个元素，并检查其连续数字是否相同，如果连续数字相同则递增计数器，如果找到不同的数字则中断内循环。
每次内循环结束或中断时，结果变量都会递增，最后显示结果变量中的结果。
示例
#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 << "Number of subarrays having minimum and maximum elements same:" << result;
return 0;
}输出
Number of subarrays having minimum and maximum elements same: 9 Time complexity = 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 << "Number of subarrays having minimum and maximum elements same:" << result;
return 0;
}输出
Number of subarrays having minimum and maximum elements same: 9 Time complexity : O(n)
上述代码的解释
在此代码中，我们将数组的第 0 个索引存储在 temp 变量中，并从索引 1 开始循环。我们检查 temp 变量是否等于当前索引处的元素，并为找到的相同数字递增计数器。如果 temp 变量不等于索引元素，那么我们找到可以从相同数字的计数中生成的子数组组合，并将结果存储在结果变量中。我们将 temp 值更改为当前索引，并将计数器重置为 1。最后，我们显示存储在结果变量中的答案。
结论
在本文中，我们解决了一个问题，即查找最小和最大元素相同的子数组个数。我们还学习了针对此问题的 C++ 程序以及我们解决此问题的完整方法（普通方法和高效方法）。我们可以使用 C、Java、Python 和其他语言编写相同的程序。希望本文对您有所帮助。
437 次浏览
