作者：稻米屋321 | 来源：互联网 | 2023-09-13 04:17
为每个最小的数组元素计算子数组数量原文：https://www.
为每个最小的数组元素计算子数组数量
原文：https://www.geeksforgeeks.org/count-subarrays-for-every-array-element-in-which-they-are-the-minimum/
给定一个数组arr[]，该数组由N个整数组成，任务是创建大小为N的数组brr[]，其中brr[i]代表arr[i]是最小元素的子数组的数量。
示例：
输入：arr[] = {3, 2, 4}
输出：{1, 3, 1}
说明：对于arr[0]，只有一个子数组，其中 3 是最小的（{3}）。
对于arr[1]，存在三个这样的子数组，其中 2 是最小的（{2}, {3, 2}, {2, 4}）。
对于arr[2]，只有一个子数组，其中 4 最小（{4}）。
输入：arr[] = {1, 2, 3, 4, 5}
输出：{5, 4, 3, 2, 1}
朴素的方法：最简单的方法是生成给定数组的所有子数组，并对每个数组元素arr[i]计数最小元素是它的子数组数。
时间复杂度：O(N ^ 3)。
辅助空间：O(n)。
高效方法：为了优化上述方法，其思想是找到每个元素的边界索引，直到它是最小的元素。 对于每个元素，令L和R分别为左侧和右侧的边界索引，直到arr[i]最小。 因此，可以通过以下方式计算所有子数组的数量：
(L + R + 1) * (R + 1)
请按照以下步骤解决问题：
将数组元素的所有索引存储在映射中。
以升序对数组排序。
初始化数组boundary[]。
遍历排序后的数组arr[]，然后使用二分搜索插入该元素的索引。 假设它插入到索引i，则其左边界为boundary[i – 1]，其右边界为boundary[i + 1]。
现在，使用上面的公式，找到子数组的数量，并在结果数组中跟踪该计数。
完成上述步骤后，打印存储在结果数组中的所有计数。
下面是上述方法的实现：
C++ 14
// C++14 program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the boundary of every
// element within which it is minimum
int binaryInsert(vector<int> &boundary, int i)
{
int l = 0;
int r = boundary.size() - 1;
// Perform Binary Search
while (l <= r)
{
// Find mid m
int m = (l + r) / 2;
// Update l
if (boundary[m] < i)
l = m + 1;
// Update r
else
r = m - 1;
}
// Inserting the index
boundary.insert(boundary.begin() + l, i);
return l;
}
// Function to required count subarrays
vector<int> countingSubarray(vector<int> arr, int n)
{
// Stores the indices of element
unordered_map<int, int> index;
for(int i = 0; i < n; i++)
index[arr[i]] = i;
vector<int> boundary = {-1, n};
sort(arr.begin(), arr.end());
// Initialize the output array
vector<int> ans(n, 0);
for(int num : arr)
{
int i = binaryInsert(boundary, index[num]);
// Left boundary, till the
// element is smallest
int l = boundary[i] - boundary[i - 1] - 1;
// Right boundary, till the
// element is smallest
int r = boundary[i + 1] - boundary[i] - 1;
// Calculate the number of subarrays
// based on its boundary
int cnt = l + r + l * r + 1;
// Adding cnt to the ans
ans[index[num]] += cnt;
}
return ans;
}
// Driver Code
int main()
{
int N = 5;
// Given array arr[]
vector<int> arr = { 3, 2, 4, 1, 5 };
// Function call
auto a = countingSubarray(arr, N);
cout << "[";
int n = a.size() - 1;
for(int i = 0; i < n; i++)
cout << a[i] << ", ";
cout << a[n] << "]";
return 0;
}
// This code is contributed by mohit kumar 29
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the boundary of every
// element within which it is minimum
static int binaryInsert(ArrayList<Integer> boundary,
int i)
{
int l = 0;
int r = boundary.size() - 1;
// Perform Binary Search
while (l <= r)
{
// Find mid m
int m = (l + r) / 2;
// Update l
if (boundary.get(m) < i)
l = m + 1;
// Update r
else
r = m - 1;
}
// Inserting the index
boundary.add(l, i);
return l;
}
// Function to required count subarrays
static int[] countingSubarray(int[] arr,
int n)
{
// Stores the indices of element
Map<Integer, Integer> index = new HashMap<>();
for(int i = 0; i < n; i++)
index.put(arr[i], i);
ArrayList<Integer> boundary = new ArrayList<>();
boundary.add(-1);
boundary.add(n);
Arrays.sort(arr);
// Initialize the output array
int[] ans = new int[n];
for(int num : arr)
{
int i = binaryInsert(boundary,
index.get(num));
// Left boundary, till the
// element is smallest
int l = boundary.get(i) -
boundary.get(i - 1) - 1;
// Right boundary, till the
// element is smallest
int r = boundary.get(i + 1) -
boundary.get(i) - 1;
// Calculate the number of subarrays
// based on its boundary
int cnt = l + r + l * r + 1;
// Adding cnt to the ans
ans[index.get(num)] += cnt;
}
return ans;
}
// Driver code
public static void main (String[] args)
{
int N = 5;
// Given array arr[]
int[] arr = { 3, 2, 4, 1, 5 };
// Function call
int[] a = countingSubarray(arr, N);
System.out.print("[");
int n = a.length - 1;
for(int i = 0; i < n; i++)
System.out.print(a[i] + ", ");
System.out.print(a[n] + "]");
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach
# Function to find the boundary of every
# element within which it is minimum
def binaryInsert(boundary, i):
l = 0
r = len(boundary) - 1
# Perform Binary Search
while l <= r:
# Find mid m
m = (l + r) // 2
# Update l
if boundary[m] < i:
l = m + 1
# Update r
else:
r = m - 1
# Inserting the index
boundary.insert(l, i)
return l
# Function to required count subarrays
def countingSubarray(arr, n):
# Stores the indices of element
index = {}
for i in range(n):
index[arr[i]] = i
boundary = [-1, n]
arr.sort()
# Initialize the output array
ans = [0 for i in range(n)]
for num in arr:
i = binaryInsert(boundary, index[num])
# Left boundary, till the
# element is smallest
l = boundary[i] - boundary[i - 1] - 1
# Right boundary, till the
# element is smallest
r = boundary[i + 1] - boundary[i] - 1
# Calculate the number of subarrays
# based on its boundary
cnt = l + r + l * r + 1
# Adding cnt to the ans
ans[index[num]] += cnt
return ans
# Driver Code
N = 5
# Given array arr[]
arr = [3, 2, 4, 1, 5]
# Function Call
print(countingSubarray(arr, N))
C
// C# program for
// the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// Function to find the
// boundary of every element
// within which it is minimum
static int binaryInsert(ArrayList boundary,
int i)
{
int l = 0;
int r = boundary.Count - 1;
// Perform Binary Search
while (l <= r)
{
// Find mid m
int m = (l + r) / 2;
// Update l
if ((int)boundary[m] < i)
l = m + 1;
// Update r
else
r = m - 1;
}
// Inserting the index
boundary.Insert(l, i);
return l;
}
// Function to required count subarrays
static int[] countingSubarray(int[] arr,
int n)
{
// Stores the indices of element
Dictionary<int,
int> index = new Dictionary<int,
int>();
for(int i = 0; i < n; i++)
index[arr[i]] = i;
ArrayList boundary = new ArrayList();
boundary.Add(-1);
boundary.Add(n);
Array.Sort(arr);
// Initialize the output array
int[] ans = new int[n];
foreach(int num in arr)
{
int i = binaryInsert(boundary,
index[num]);
// Left boundary, till the
// element is smallest
int l = (int)boundary[i] -
(int)boundary[i - 1] - 1;
// Right boundary, till the
// element is smallest
int r = (int)boundary[i + 1] -
(int)boundary[i] - 1;
// Calculate the number of
// subarrays based on its boundary
int cnt = l + r + l * r + 1;
// Adding cnt to the ans
ans[index[num]] += cnt;
}
return ans;
}
// Driver code
public static void Main(string[] args)
{
int N = 5;
// Given array arr[]
int[] arr = {3, 2, 4, 1, 5};
// Function call
int[] a = countingSubarray(arr, N);
Console.Write("[");
int n = a.Length - 1;
for(int i = 0; i < n; i++)
Console.Write(a[i] + ", ");
Console.Write(a[n] + "]");
}
}
// This code is contributed by Rutvik_56
输出：
时间复杂度：O(n Log n)。
辅助空间：O(n)。
京公网安备 11010802041100号