为了不断优化推荐效果，今日头条每天要存储和处理海量数据。假设有这样一种场景：我们对用户按照它们的注册时间先后来标号，对于一类文章，每个用户都有不同的喜好值，我们会想知道某一段时间内注册的用户（标号相连的一批用户）中，有多少用户对这类文章喜好值为k。因为一些特殊的原因，不会出现一个查询的用户区间完全覆盖另一个查询的用户区间(不存在L1<=L2<=R2<=R1)。
[编程题]用户喜好
- 热度指数：4016 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
输入： 第1行为n代表用户的个数 第2行为n个整数，第i个代表用户标号为i的用户对某类文章的喜好度 第3行为一个正整数q代表查询的组数 第4行到第（3+q）行，每行包含3个整数l,r,k代表一组查询，即标号为l<=i<=r的用户中对这类文章喜好值为k的用户的个数。 数据范围n <= 300000,q<=300000 k是整型
输出描述:
输出：一共q行，每行一个整数代表喜好值为k的用户的个数
示例1
输入
5 1 2 3 3 5 3 1 2 1 2 4 5 3 5 3
输出
1 0 2
说明
样例解释: 有5个用户，喜好值为分别为1、2、3、3、5， 第一组询问对于标号[1,2]的用户喜好值为1的用户的个数是1 第二组询问对于标号[2,4]的用户喜好值为5的用户的个数是0 第三组询问对于标号[3,5]的用户喜好值为3的用户的个数是2
#解析：https://blog.csdn.net/weixin_42001089/article/details/87114410 _ = input()
arr = []
d = {}
for e in input().split():
arr.append(int(e))
d[int(e)] = 0
n = int(input())
temp = []
for i in range(n):
e = input().split()
e[0] = int(e[0])-1
e[1] = int(e[1])-1
e[2] = int(e[2])
temp.append(e+[i])
temp.sort()
result = []
left = 0
right = -1
arr[0] = 1
for i in range(n):
tempList = temp[i]
left_interval = tempList[0] - left
right_interval = tempList[1] - right
for l in range(left_interval):
d[arr[left+l]]-=1
for r in range(right_interval):
d[arr[right+r+1]]+=1
if tempList[2] in d:
result.append([d[tempList[2]],tempList[3]])
else:
result.append([0,tempList[3]])
left = tempList[0]
right = tempList[1]
result = sorted(result,key = lambda x:x[1])
for i in range(n):
print(result[i][0])
编辑于 2019-02-13 14:40:25
回复(1)
//提交时间：2020-09-04 语言：C 运行时间： 1572 ms 占用内存：4172K 状态：答案正确
#include <stdio.h>
int main(){
int n,i,q,l,r,k;
scanf("%d",&n);
int like[n];
for(i=0;i<n;i++){
scanf("%d",&like[i]);
}
scanf("%d",&q);
for(int j=0;j<q;j++){
int count=0;
scanf("%d%d%d",&l,&r,&k);
for(int t=l-1;t<r;t++){
if(like[t]==k){
count++;
}
}
printf("%d\n",count);
}
return 0;
}
#include <stdio.h>
int main(){
int n,i,q,l,r,k;
scanf("%d",&n);
int like[n];
for(i=0;i<n;i++){
scanf("%d",&like[i]);
}
scanf("%d",&q);
for(int j=0;j<q;j++){
int count=0;
scanf("%d%d%d",&l,&r,&k);
for(int t=l-1;t<r;t++){
if(like[t]==k){
count++;
}
}
printf("%d\n",count);
}
return 0;
}
编辑于 2020-09-04 16:37:12
回复(0)
if __name__ == '__main__':
n = int(input())
st = {}
arr = list(map(int,input().split()))
for i in range(n):
if arr[i] in st:
st[arr[i]].append(i+1)
else:
st[arr[i]] = [i+1]
q = int(input())
b = []
for i in range(q):
brr = list(map(int,input().split()))
l,r,k = brr[0],brr[1],brr[2]
if k in st:
c = st[k]
count = 0
for ci in c:
if l<=ci<=r:
count += 1
b.append(count)
else:
b.append(0)
for ij in b:
print(ij)
直接暴力求解是50%，使用倒排的思想，将n的表放入到hash表里，并且为了保存多个值，用list存放index位置。就可以达到100%通过
发表于 2020-08-12 16:31:28
回复(0)
运行时间超出，那位大神能告知_ = int(input().strip()) de_like = list(map(int, input().strip().split())) q = int(input().strip()) search_data = [] for i in range(q): search_data.append(list(map(int, input().strip().split()))) for i in search_data: l, r, k = i num = 0 print(de_like[l-1:r].count(k))
发表于 2018-08-22 22:33:13
回复(2)
#include <iostream>
using namespace std;
int main()
{
int n;
while(cin>>n)
{
int like[n];
for (int i=0; i<=n-1; i++)
cin>>like[i];
int q;
cin>>q;
for (int i=0; i<q; i++)
{
int l,r,k;
cin>>l>>r>>k;
int counts=0;
for (int j=l-1; j<=r-1; j++)
{
if (like[j]==k)
counts++;
}
cout << counts << endl;
}
}
return 0;
}
编辑于 2018-05-11 16:16:34
回复(7)
/*
1、首先存储的时候，每个喜好值分别一个vector，分别存入map中，对于每个喜好值的vector，存入的是，用户的id，因为输入是从小到大输入的，所以就可以保证vector有序，然后用二分查找区间的左右端点。
2、这里的二分不是常规的二分查找，对于区间左端点，在vector查找的是小于target的点的最大下标，如果target小于vector最小值，直接返回-1
3、对于区间右端点，查找的是小于等于target的最大下标，如果target大于vector的最大值，直接返回vector最大值的下标
*/
#include<iostream>
#include<map>
#include<vector>
using namespace std;
int find_low(vector<int>& v,int target){
int low=0;
int high=v.size()-1;
int mid;
if(target<=v[low]) return -1;
if(target>v[high]) return high;
while(low<high){
mid=(low+high+1)>>1;
//cout<<low<<" "<<high<<" "<<mid<<endl;
if(target<=v[mid]){
high=mid-1;
}else{
low=mid;
}
}
return high;
}
int find_high(vector<int>& v,int target){
int low=0;
int high=v.size()-1;
int mid;
if(target<v[low]) return -1;
if(target>=v[high]) return high;
while(low<high){
mid=(low+high+1)>>1;
//cout<<low<<" "<<high<<" "<<mid<<endl;
if(target==v[mid]){
return mid;
}else if(target<v[mid]){
high=mid-1;
}else{
low=mid;
}
}
return high;
}
int main()
{
int n,q,t;
map<int,vector<int> > count;
cin>>n;
for(int i=1;i<=n;i++){
cin>>t;
if(count.count(t)==0){
vector<int> v;
v.push_back(i);
count[t]=v;
}else{
count[t].push_back(i);
}
}
cin>>q;
int l,r,k;
int sum;
for(int i=0;i<q;i++){
cin>>l>>r>>k;
sum=0;
if(count.count(k)>0){
vector<int> v=count[k];
int low=find_low(v,l);
int high=find_high(v,r);
//cout<<low<<" "<<high<<endl;
sum=high-low;
}
cout<<sum<<endl;
}
return 0;
}
编辑于 2018-06-08 16:44:37
回复(1)
# 一个简单的Python实现，输入数据的时候用字典存起来，然后搜索只用去查找字典里的对应项
n = int(input())
user_list = [int(x) for x in input().split()]
q = int(input())
find = [[int(x) for x in input().split()] for _ in range(q)]
dic = {}
for i in range(n):
try:
dic[user_list[i]].append(i + 1)
except:
dic[user_list[i]] = [i + 1]
result_list = []
for i in range(q):
l, r , k = find[i]
if k not in dic:
result = 0
else:
temp = dic[k]
result = 0
if temp[-1] < l or temp[0] > r:
pass
else:
for i in range(len(temp)):
if l <= temp[i] <= r:
result += 1
result_list.append(result)
for r in result_list:
print(r)
发表于 2019-04-14 00:01:03
回复(0)
import java.util.Scanner;
import java.util.HashMap;
import java.util.ArrayList;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
HashMap<Integer, ArrayList<Integer>> user_like_list = new HashMap<>();
for (int i = 0; i < n; i++) {
int like = in.nextInt();
if (user_like_list.get(like) == null) {
user_like_list.put(like, new ArrayList());
}
user_like_list.get(like).add(i+1);
}
int q = in.nextInt();
for (int i = 0; i < q; i++) {
int res = 0;
int l = in.nextInt();
int r = in.nextInt();
int k = in.nextInt();
if (user_like_list.get(k) != null) {
for (int j = 0; j < user_like_list.get(k).size(); j++) {
int t = user_like_list.get(k).get(j);
if (t >= l && t <= r) res++;
}
}
System.out.println(res);
}
}
}
发表于 2024-06-08 18:04:31
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int n = in.nextInt();//用户数
int[] users = new int[n];//用户喜好度
for (int i = 0; i < n; i++) users[i] = in.nextInt();
int m = in.nextInt();
// int[][] da = new int[m][3];
for (int i = 0; i < m; i++) {
// for(int j = 0; j < 3; j++){
int start = (in.nextInt());
int end = (in.nextInt());
int p = (in.nextInt());
int cou = 0;
// 限时处理，减少空间复杂度，但是也要考虑缓存换页的情况
for (int k = start - 1; k < end && k < n; k++) {
// System.out.println("start:" + start + ",end: "+ end + ",k:"+k +",users[p.intValue()]: " + users[k.intValue()]);
if (users[k] == p)cou++;
}
System.out.println(cou);
// da[i][j] = in.nextInt();
// }
}
// 数据处理完成
}
}
发表于 2023-10-22 10:27:29
回复(0)
n=int(input().strip()) like=list(map(int, input().strip().split())) q=int(input().strip()) A=[] for i in range(q): A.append(list(map(int, input().strip().split()))) for i in range(len(A)): print(like[A[i][0]-1:A[i][1]].count(A[i][2]))
发表于 2021-05-26 10:10:24
回复(0)
#include <stdio.h>
#include <stdlib.h>
int main(){
int custom_nums,query_nums,i,j,k;
int *custom;
int **query;
scanf("%d",&custom_nums);
custom = (int *)malloc(sizeof(int)*custom_nums);
for(i=0;i<custom_nums;i++){
scanf("%d",&custom[i]);
}
scanf("%d",&query_nums);
query=(int **)malloc(sizeof(int *)*query_nums);
for(i=0;i<query_nums;i++){
query[i]=(int *)malloc(sizeof(int)*3);
for(j=0;j<3;j++){
scanf("%d",&query[i][j]);
}
}
for (i = 0;i < query_nums;i++) {
k = 0;
for (j = query[i][0]-1;j <= (query[i][1] - query[i][0] + query[i][0] - 1);j++) {
if (query[i][2] == custom[j]) k++;
}
printf("%d\n", k);
}
free(custom);
for(i=0;i<query_nums;i++){
free(query[i]);
}
free(query);
}
发表于 2021-03-07 16:09:53
回复(1)
首先观察到用户总数为3e5个，然后查询次数也是3e5，所以直接暴力是不行的。我本来想用线段树维护区间k个数的，但n=3e5连线段树都开不了。实际上这题只要用二分查找就行了，先将原序列中的每一个k在原序列的位置记录到对应的k向量后面，然后查询区间的时候，先判断输入的k是否存在，然后直接lower_bound左边界l和upper_bound右边界r在a[k]中的位置，此时的r1-l1就是答案。最后由于本题没给出k的范围，所以要对原序列的每一个k做离散化处理（具体见代码）
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
vector<int> a[300005];
int cc[300005],b[300005];
int n,x,q;
int main(){
cin>>n;
for (int i=1; i<=n; i++){
scanf("%d",&cc[i]);
b[i]=cc[i];
//a[x].pb(i);
}
sort(cc+1,cc+n+1);
int siz=unique(cc+1,cc+n+1)-cc-1;
for (int i=1; i<=n; i++){
int p=lower_bound(cc+1,cc+1+n,b[i])-cc-1;
a[p].pb(i);
}
cin>>q;
int l,r,v,ans,l1,r1;
while (q--){
scanf("%d%d%d",&l,&r,&v);
int p=lower_bound(cc+1,cc+1+n,v)-cc-1;
if (cc[p+1]!=v){
cout<<0<<endl;
continue;
}
l1=lower_bound(a[p].begin(),a[p].end(),l)-a[p].begin();
r1=upper_bound(a[p].begin(),a[p].end(),r)-a[p].begin();
ans=r1-l1;
cout<<ans<<endl;
}
return 0;
}
发表于 2021-01-23 15:28:46
回复(0)
#采用字典
n = int(input())
xihao = list(map(int,input().split()))
dct = {}
for i in range(n):
if xihao[i] not in dct.keys():
dct[xihao[i]] = [i]
else:
dct[xihao[i]].append(i)
q = int(input())
res = []
for i in range(q):
l,r,k = list(map(int,input().split()))
count = 0
try:
tmp = dct[k]
# print(tmp)
for j in range(len(tmp)):
if tmp[j] <= r-1 and tmp[j] >= l-1:
count += 1
except:
pass
res.append(count)
for r in res:
print(r)
发表于 2019-08-09 14:29:44
回复(0)
想知道为什么总是本地能过通过，牛客的系统就是出错呢。本地调试看过很多种用例情况应该不出现越界可是报错总是说数组越界。
importjava.util.Scanner;
importjava.util.List;
importjava.util.ArrayList;
importjava.util.Arrays;
public class Main{
public void main(String[] args) { Scanner input = newScanner(System.in); Scanner s = newScanner(System.in); intN = input.nextInt(); List user_list = newArrayList(); List user_like_list = newArrayList(); String sentence = s.nextLine(); String[] num_pair = sentence.split(" "); for(inti =0; i<N;i++) user_like_list.add(Integer.valueOf(num_pair[i])); int row = input.nextInt(); for(inti =0; i<row;i++) { String like = s.nextLine(); String[] like_pair = like.split(" "); user_list.add(Integer.valueOf(like_pair[0])); user_list.add(Integer.valueOf(like_pair[1])); user_list.add(Integer.valueOf(like_pair[2])); } for(inti = 0; i < row;i++) { intcount = 0; intl = user_list.get(0+ i * 3) - 1; intr = user_list.get(1+ i * 3) - 1; intk = user_list.get(2+ i * 3); for(intj = l;j <= r ;j++) { intuser_i_like = user_like_list.get(j); if(user_i_like == k) count ++; } System.out.println(count); }
}
}
编辑于 2019-04-13 02:04:44
回复(0)
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
int main()
{
int n;int q;
while (cin >> n)
{
vector<int> score;
for (int i = 0; i <= n-1; i++)
{
int a; cin>>a;
score.push_back(a);// scanf("%d, &score[i]);
//不能用 cin>>score[i]; 没有重载
}
cin>>q;
for(int i=0; i<q; i++)
{
int l,r,k;
cin>>l>>r>>k;//scanf("%d%d%d", &l, &r, &k);
int res = 0;
for(int j=l-1; j<=r-1; j++)
{
if(score[j]==k)
res++;
}
cout<<res<<endl; //printf("%d\n", res);
}
}
return 0;
}
发表于 2019-03-15 12:39:56
回复(0)
check_list=[] user=[] n = eval(input()) list_n = list(map(int, input().split(' '))) q = int(input())for i in range(q): a = list(map(int, input().split(' '))) user.append(a[:2]) check_list.append(a[-1])for j in range(q): m = list_n[user[j][0]-1:user[j][1]-1] result=m.count(check_list[j]) print(result)
编辑于 2019-03-15 10:53:05
回复(1)
import bisect
n = int(input())
l = list(map(int, input().split()))
q = int(input())
keys = list(set(l))
score_dict = {}
for k in keys:
score_dict[k] = []
for i in range(n):
score_dict[l[i]].append(i)
q_l = []
for q_i in range(q):
q_l.append(list(map(int, input().split())))
for q_i in range(q):
l, r, k = q_l[q_i]
if k in score_dict:
print(bisect.bisect(score_dict[k], r-1) - bisect.bisect_left(score_dict[k], l-1))
else:
print(0)
编辑于 2018-10-29 18:03:44
回复(0)
import sysn =int(sys.stdin.readline().strip())l =map(int, sys.stdin.readline().strip().split())m =int(sys.stdin.readline().strip())for i in range(m):s =map(int, sys.stdin.readline().strip().split())ind1,ind2,f =s[0]-1, s[1]-1, s[2]a =filter(lambdax: x ==s[2], l[ind1:ind2+1])print len(a)
发表于 2018-09-10 19:04:56
回复(1)
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
int main() {
int n, q;
while (cin >> n) {
vector<int> users(n + 1);
for (int i = 1; i <= n; i++) {
scanf("%d", &users[i]);
}
cin >> q;
int l, r, k;
for (int i = 0; i < q; i++) {
scanf("%d%d%d", &l, &r, &k);
int res = 0;
while (l <= r) {
res += users[l++] == k ? 1 : 0;
}
printf("%d\n", res);
}
}
}
编辑于 2018-08-22 17:15:17
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
