(coordinate dynamic programming) lintcode medium 248 · count the number of numbers smaller than a given integer

subject

describe
Given an array of integers （ Subscript by 0 To n-1, among n Represents the size of the array , The range of values is 0 To 10000）, And one. Query list . For every query , I'll give you an integer , Please return the number of elements in the array less than the given integer .

Examples

Examples 1:

 Input : array =[1,2,7,8,5] queries =[1,8,5]
 Output :[0,4,2]

Examples 2:

 Input : array =[3,4,5,8] queries =[2,4]
 Output :[0,1]

analysis

The maximum number in the given array is 10000, Then we can use the hash table to count the number of each value , We think if the number to be compared is greater than 10000, Then it is larger than all the numbers in a given array , Here we can use coordinate dynamic programming
Coordinate dynamic programming , The hash table counts the number of values in a given array , state f[i] i Represents the current number to be calculated f[i] The value of represents the ratio i The number of small numbers Transfer equation f[i]=f[i-1]+hash[i-1] For example, we calculate the ratio 10 The number of small numbers Just know better than 9 Small number plus 9 The number of
The maximum value in the given array 10000 therefore f[i] When i>10000 Its value must be f[10001] It can also be understood as larger than all values in a given array

#include <bits/stdc++.h>
using namespace std;

class Solution {
    
public:
    vector<int> countOfSmallerNumber(vector<int> &a, vector<int> &queries) {
    
        vector<int> hash_map(10001,0);	// Number of values 
		for(int i=0;i<a.size();i++)
		{
    
			hash_map[a[i]]+=1;
		}
		
		vector<int> f(10002,0);		// state   Represents the number of values smaller than the current value 
		
		for(int i=1;i<10002;i++)
			f[i]=f[i-1]+hash_map[i-1];	// Last state + The number of previous values 
			
		vector<int> ans;
		for(int i=0;i<queries.size();i++)
		{
    
			int val=queries[i];
			if(val>10001)
			{
    
				ans.push_back(f[10001]);
				continue;
			}
			ans.push_back(f[val]);
		} 
		
		return ans;
    }
};

int main (void)
{
    
	vector<int> a={
    1,2,7,8,5};
	vector<int> q={
    1,8,5};
	vector<int> ans;
	Solution s;
	ans=s.countOfSmallerNumber(a,q);
	
	for(int i=0;i<ans.size();i++)
		cout<<ans[i]<<" ";
		
	return 0;
}

summary

It was originally a question of practicing line segment tree , The sudden whim uses coordinate dynamic programming , It is found that this method is the most efficient for this problem