使用C ++查找其最小值和最大值相同的子数组的数量
在本文中,我们将使用 C++ 解决求最大和最小元素相同的子数组个数的问题。这是问题的示例 -
Input : array = { 2, 3, 6, 6, 2, 4, 4, 4 }Output : 12Explanation : {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 : 9Explanation : {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 << "最小和最大元素相同的子数组数:" << result; return 0; }
输出结果
最小和最大元素相同的子数组数: 9Time 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 << "最小和最大元素相同的子数组数:" << result; return 0; }
输出结果
最小和最大元素相同的子数组数: 9Time complexity : O(n)
上面代码的解释
在这段代码中,我们将数组的第 0 个索引存储在 temp 变量中,并从索引 1 开始循环。我们检查 temp 变量是否等于当前索引处的元素,并对找到的相同数字将 count 增加 1。如果临时变量不等于索引元素,那么我们找到可以由相同数字的计数组成的子数组的组合,并将结果存储在结果变量中。我们将临时值更改为当前索引重置计数为 1。最后,我们将显示存储在结果变量中的答案。
结论
在这篇文章中,我们解决了一个问题,找到最小和最大元素相同的子数组的数量。我们还学习了这个问题的 C++ 程序以及我们解决这个问题的完整方法(正常和高效)。我们可以用其他语言编写相同的程序,例如 C、java、python 和其他语言。希望这篇文章对您有所帮助。