计算具有与C ++中原始数组相同的不同元素的子数组
给我们一个包含整数的数组arr[]。目的是计算arr[]的所有子数组,以使每个子数组中的不同元素数与原始数组中的不同元素数相同。如果原始数组为[1,1,2,3],则子数组将为[1,2,3]和[1,1,2,3]。
原始数组中的不同元素总数为3。两个子数组中的不同元素总数也为3。
让我们通过示例来理解。
输入−arr[]={1,2,1,2,3,4,2};
输出-具有与原始数组相同的不同元素的子数组的计数为-6
说明-arr[]中的不同元素是4(1,2,3,4)。具有相同数量的不同元素的子数组是:(从左到右计数不同)
[1,2,1,2,3,4], [2,1,2,3,4], [1,2,3,4], [1,2,3,4,2], [2,1,2,3,4,2], [1,2,1,2,3,4,2 ]
输入−arr[]={8,7,5,6,10};
输出-具有与原始数组相同的不同元素的子数组的计数为-1
说明-arr[]中的不同元素为5(5,6,7,8,10)。具有相同数量的不同元素的子数组是:(从左到右计数不同)[8,7,6,5,10]。仅1
以下程序中使用的方法如下
取整数的数组arr[]并计算数组的大小。
函数sub_ele_diff_one(intarr[],intsize)获取数组,并返回连续元素相差1的子数组计数。
进行临时变量计数,并向左和向右进行变量。
使用类型为unordered_map的变量来创建随机对。
从0开始循环FOR,直到一个数组的大小为止,并在其中设置unordered_map内部的arr[i]值。
现在,计算unordered_map的大小并清除unordered_map。
从0开始启动FOR循环,直到数组大小为止。
在循环内,开始WHILE直到unordered_map的right<size和left<size
预增um[arr[right]]的值
现在,检查um[arr[right]]=1,然后将left的值预加1。
在WHILE之外,将right的值预加1。
检查IF左边=unordered_map的大小,然后将count设置为count+size-right+1
将um[arr[i]]减1
检查IFum[arr[i]]=0,然后将左减1
返回计数
打印结果。
示例
#include <bits/stdc++.h> using namespace std; int sub_distinct(int arr[], int size){ int count = 0, right = 0, left = 0; unordered_map<int, int> um; for (int i = 0; i < size; ++i){ um[arr[i]] = 1; } int um_size = um.size(); um.clear(); for(int i = 0; i < size; ++i){ while (right < size && left < um_size){ ++um[arr[right]]; if (um[arr[right]] == 1){ ++left; } ++right; } if (left == um_size){ count = count + (size - right + 1); } --um[arr[i]]; if (um[arr[i]] == 0){ --left; } } return count; } int main(){ int arr[] = {4, 3, 2, 5}; int size = sizeof(arr) / sizeof(arr[0]); cout<<"Count of subarrays having total distinct elements same as original array are: "<<sub_distinct(arr, size); return 0; }
输出结果
如果我们运行上面的代码,它将生成以下输出-
Count of subarrays having total distinct elements same as original array are: 1