数组范围查询频率与值相同的元素

本文概述

建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
C ++
Java
Python3
C#

给定一个由N个数字组成的数组, 任务是回答以下类型的Q个查询：

query(start, end) = Number of times a number x occurs exactly x times in a subarray from start to end

例子：

输入：arr = {1, 2, 2, 2, 3, 3, 3}查询1：开始= 0, 结束= 1, 查询2：开始= 1, 结束= 1, 查询3：开始= 0, 结束= 2, 查询4：开始= 1, 结束= 3, 查询5：开始= 3, 结束= 5, 查询6：开始= 0, 结束= 5输出：1 0 2 1 1 3说明在查询1中, 元素1出现一次子数组[1, 2]; 在查询2中, 没有元素满足要求的条件是子数组[2]；在查询3中, 元素1在子数组[1、2、2]中发生一次, 而元素2发生两次。在查询4中, 元素2在子数组[2, 2, 3]中出现两次；在查询5中, 元素3在子数组[3、3、3]中出现三次；在查询6中, 元素1在子数组[1、2、2、3、3、3]中发生一次, 2发生两次, 3发生三次

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。方法1(蛮力)
计算每个查询下子数组中每个元素的频率。如果在每个查询覆盖的子数组中任何数字x的频率为x, 我们将增加计数器。
C ++

/* C++ Program to answer Q queries to find number of times an element x appears x times in a Query subarray */ #include < bits/stdc++.h> using namespace std; /* Returns the count of number x with frequency x in the subarray from start to end */ int solveQuery( int start, int end, int arr[]) { // map for frequency of elements unordered_map< int , int > frequency; // store frequency of each element // in arr[start; end] for ( int i = start; i < = end; i++) frequency[arr[i]]++; // Count elements with same frequency // as value int count = 0; for ( auto x : frequency) if (x.first == x.second) count++; return count; }int main() { int A[] = { 1, 2, 2, 3, 3, 3 }; int n = sizeof (A) / sizeof (A[0]); // 2D array of queries with 2 columns int queries[][3] = { { 0, 1 }, { 1, 1 }, { 0, 2 }, { 1, 3 }, { 3, 5 }, { 0, 5 } }; // calculating number of queries int q = sizeof (queries) / sizeof (queries[0]); for ( int i = 0; i < q; i++) { int start = queries[i][0]; int end = queries[i][1]; cout < < "Answer for Query " < < (i + 1) < < " = " < < solveQuery(start, end, A) < < endl; }return 0; }

Java

/* Java Program to answer Q queries to find number of times an element x appears x times in a Query subarray */ import java.util.HashMap; import java.util.Map; class GFG {/* Returns the count of number x with frequency x in the subarray from start to end */ static int solveQuery( int start, int end, int arr[]) { // map for frequency of elements Map< Integer, Integer> mp = new HashMap< > (); // store frequency of each element // in arr[start; end] for ( int i = start; i < = end; i++) mp.put(arr[i], mp.get(arr[i]) == null ? 1 :mp.get(arr[i])+ 1 ); // Count elements with same frequency // as value int count = 0 ; for (Map.Entry< Integer, Integer> entry : mp.entrySet()) if (entry.getKey() == entry.getValue()) count++; return count; }// Driver code public static void main(String[] args) { int A[] = { 1 , 2 , 2 , 3 , 3 , 3 }; int n = A.length; // 2D array of queries with 2 columns int [][]queries = { { 0 , 1 }, { 1 , 1 }, { 0 , 2 }, { 1 , 3 }, { 3 , 5 }, { 0 , 5 } }; // calculating number of queries int q = queries.length; for ( int i = 0 ; i < q; i++) { int start = queries[i][ 0 ]; int end = queries[i][ 1 ]; System.out.println( "Answer for Query " + (i + 1 ) + " = " + solveQuery(start, end, A)); } } }// This code is contributed by Rajput-Ji

Python3

# Python 3 Program to answer Q queries # to find number of times an element x # appears x times in a Query subarray import math as mt# Returns the count of number x with # frequency x in the subarray from # start to end def solveQuery(start, end, arr):# map for frequency of elements frequency = dict ()# store frequency of each element # in arr[start end] for i in range (start, end + 1 ):if arr[i] in frequency.keys(): frequency[arr[i]] + = 1 else : frequency[arr[i]] = 1# Count elements with same # frequency as value count = 0 for x in frequency: if x = = frequency[x]: count + = 1 return count# Driver code A = [ 1 , 2 , 2 , 3 , 3 , 3 ] n = len (A)# 2D array of queries with 2 columns queries = [[ 0 , 1 ], [ 1 , 1 ], [ 0 , 2 ], [ 1 , 3 ], [ 3 , 5 ], [ 0 , 5 ]]# calculating number of queries q = len (queries)for i in range (q): start = queries[i][ 0 ] end = queries[i][ 1 ] print ( "Answer for Query " , (i + 1 ), " = " , solveQuery(start, end, A))# This code is contributed # by Mohit kumar 29

// C# Program to answer Q queries to // find number of times an element x // appears x times in a Query subarray using System; using System.Collections.Generic; class GFG { /* Returns the count of number x with frequency x in the subarray from start to end */ public static int solveQuery( int start, int end, int [] arr) {// map for frequency of elements Dictionary< int , int > mp = new Dictionary< int , int > (); // store frequency of each element // in arr[start; end] for ( int i = start; i < = end; i++) { if (mp.ContainsKey(arr[i])) mp[arr[i]]++; else mp.Add(arr[i], 1); }// Count elements with same frequency // as value int count = 0; foreach (KeyValuePair< int , int > entry in mp) { if (entry.Key == entry.Value) count++; } return count; }// Driver code public static void Main(String[] args) { int [] A = { 1, 2, 2, 3, 3, 3 }; int n = A.Length; // 2D array of queries with 2 columns int [, ] queries = {{ 0, 1 }, { 1, 1 }, { 0, 2 }, { 1, 3 }, { 3, 5 }, { 0, 5 }}; // calculating number of queries int q = queries.Length; for ( int i = 0; i < q; i++) { int start = queries[i, 0]; int end = queries[i, 1]; Console.WriteLine( "Answer for Query " + (i + 1) + " = " + solveQuery(start, end, A)); } } }// This code is contributed by // sanjeev2552

【数组范围查询频率与值相同的元素】输出如下：

Answer for Query 1 = 1Answer for Query 2 = 0Answer for Query 3 = 2Answer for Query 4 = 1Answer for Query 5 = 1Answer for Query 6 = 3

该方法的时间复杂度为O(Q * N)
方法2(高效)
我们可以使用
MO的算法
.
我们为每个查询分配开始索引, 结束索引和查询编号, 每个查询采用以下形式：

起始索引(L)：查询涵盖的子数组的起始索引； Ending Index(R)：查询所涵盖的子数组的Ending Index；查询编号(索引)：由于查询已排序, 因此可以告诉我们查询的原始位置, 以便我们按原始顺序回答查询

首先, 我们将查询分为多个块, 然后使用自定义比较器对查询进行排序。
现在, 我们离线处理查询, 并保留两个指针, 即
MO_RIGHT
和
MO_LEFT
对于每个传入的查询, 我们将这些指针向前和向后移动, 并根据当前查询的开始和结束索引插入和删除元素。
让当前运行的答案为current_ans.
每当我们插入一个元素, 我们增加包含元素的频率, 如果这个频率等于我们刚包含的元素, 我们增加current_ans。如果这个元素的频率变成(当前元素+ 1), 这意味着这个元素被计入当current_ans等于其频率时, 因此在这种情况下我们需要减小current_ans。
每当我们删除/删除一个元素, 我们减小被排除元素的频率, 如果该频率等于我们刚排除的元素, 则增加current_ans。如果该元素的频率变为(current element – 1), 则意味着该元素被计入较早的位置当current_ans等于其频率时, 因此在这种情况下我们需要减小current_ans。

/* C++ Program to answer Q queries to find number of times an element x appears x times in a Query subarray */ #include < bits/stdc++.h> using namespace std; // Variable to represent block size. // This is made global so compare() // of sort can use it. int block; // Structure to represent a query range struct Query { int L, R, index; }; /* Function used to sort all queries so that all queries of same block are arranged together and within a block, queries are sorted in increasing order of R values. */ bool compare(Query x, Query y) { // Different blocks, sort by block. if (x.L / block != y.L / block) return x.L / block < y.L / block; // Same block, sort by R value return x.R < y.R; }/* Inserts element (x) into current range and updates current answer */ void add( int x, int & currentAns, unordered_map< int , int > & freq) {// increment frequency of this element freq[x]++; // if this element was previously // contributing to the currentAns, // decrement currentAns if (freq[x] == (x + 1)) currentAns--; // if this element has frequency // equal to its value, increment // currentAns else if (freq[x] == x) currentAns++; }/* Removes element (x) from current range btw L and R and updates current Answer */ void remove ( int x, int & currentAns, unordered_map< int , int > & freq) {// decrement frequency of this element freq[x]--; // if this element has frequency equal // to its value, increment currentAns if (freq[x] == x) currentAns++; // if this element was previously // contributing to the currentAns // decrement currentAns else if (freq[x] == (x - 1)) currentAns--; }/* Utility Function to answer all queries and build the ans array in the original order of queries */ void queryResultsUtil( int a[], Query q[], int ans[], int m) {// map to store freq of each element unordered_map< int , int > freq; // Initialize current L, current R // and current sum int currL = 0, currR = 0; int currentAns = 0; // Traverse through all queries for ( int i = 0; i < m; i++) { // L and R values of current range int L = q[i].L, R = q[i].R; int index = q[i].index; // Remove extra elements of previous // range. For example if previous // range is [0, 3] and current range // is [2, 5], then a[0] and a[1] are // removed while (currL < L) { remove (a[currL], currentAns, freq); currL++; }// Add Elements of current Range while (currL > L) { currL--; add(a[currL], currentAns, freq); } while (currR < = R) { add(a[currR], currentAns, freq); currR++; }// Remove elements of previous range.For example // when previous range is [0, 10] and current range // is [3, 8], then a[9] and a[10] are Removed while (currR > R + 1) { currR--; remove (a[currR], currentAns, freq); }// Store current ans as the Query ans for // Query number index ans[index] = currentAns; } }/* Wrapper for queryResultsUtil() and outputs the ans array constructed by answering all queries */ void queryResults( int a[], int n, Query q[], int m) { // Find block size block = ( int ) sqrt (n); // Sort all queries so that queries of same blocks // are arranged together. sort(q, q + m, compare); int * ans = new int [m]; queryResultsUtil(a, q, ans, m); for ( int i = 0; i < m; i++) { cout < < "Answer for Query " < < (i + 1) < < " = " < < ans[i] < < endl; } }// Driver program int main() { int A[] = { 1, 2, 2, 3, 3, 3 }; int n = sizeof (A) / sizeof (A[0]); // 2D array of queries with 2 columns Query queries[] = { { 0, 1, 0 }, { 1, 1, 1 }, { 0, 2, 2 }, { 1, 3, 3 }, { 3, 5, 4 }, { 0, 5, 5 } }; // calculating number of queries int q = sizeof (queries) / sizeof (queries[0]); // Print result for each Query queryResults(A, n, queries, q); return 0; }

输出如下：