首页 > 试题广场 >

用户喜好

[编程题]用户喜好

热度指数：1309 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

为了不断优化推荐效果，今日头条每天要存储和处理海量数据。假设有这样一种场景：我们对用户按照它们的注册时间先后来标号，对于一类文章，每个用户都有不同的喜好值，我们会想知道某一段时间内注册的用户（标号相连的一批用户）中，有多少用户对这类文章喜好值为k。因为一些特殊的原因，不会出现一个查询的用户区间完全覆盖另一个查询的用户区间(不存在L1<=L2<=R2<=R1)。

输入描述:

输入： 第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

输入

输出

1
0
2

说明

样例解释:
有5个用户，喜好值为分别为1、2、3、3、5，
第一组询问对于标号[1,2]的用户喜好值为1的用户的个数是1
第二组询问对于标号[2,4]的用户喜好值为5的用户的个数是0
第三组询问对于标号[3,5]的用户喜好值为3的用户的个数是2

算法知识视频讲解

Java

Pure201911132215663

测试用例通过，但是提交后显示运行超时，求大神指点一下不合理之处在哪，感谢感谢！！

 public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] user = new int[n];
        for (int i = 0; i < n; i++) {
            user[i] = sc.nextInt();
        }
        int m = sc.nextInt();

        while (m != 0){
            int temp = 0;
            int l = sc.nextInt();
            int r = sc.nextInt();
            int k = sc.nextInt();
            for (int i = l - 1; i < r; i++) {
                if (user[i] == k){
                    temp++;
                }
            }
            System.out.println(temp);
            m--;
        }
    }
}

发表于 2021-04-02 20:07:39 回复(0)

shengmeihua

#include <iostream>
using namespace std;
const int N = 300001;
int main()
{
	int n;
	cin >> n;
	int a[N];
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	int q;
	cin >> q;
	while (q--) {
		int l, r, k;
		cin >> l >> r >> k;
		int count = 0;
		for (int i = l; i <= r; i++) {
			if (a[i] == k) {
				count = count + 1;
			}
		}
		cout << count << endl;
	}
	return 0;
}

编辑于 2020-10-11 09:12:06 回复(0)

磷加锌

let n = parseInt(readline());
let kArr = readline().split(' ');
let kObj = {}; // 存k值的对应下标数组
for (let i = 0; i < n; i++) {
    kObj[kArr[i]] = kObj[kArr[i]] ? kObj[kArr[i]] : [];
    kObj[kArr[i]].push(i);
}
let count = readline();
while(count--) {
    let arr = readline().split(' ');
    let l = arr[0];
    let r = arr[1];
    let k = arr[2];
    let res = 0;
    for (let i in kObj[k]) { // 直接搜索k值对应数组里在[l, r]范围内的个数
        if (kObj[k][i] >= l-1 && kObj[k][i] <= r-1) {
            res++;
        }
    }
    console.log(res)
}

发表于 2020-09-04 18:43:12 回复(0)

班长夏四果

case50%超时了

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
//        5
//        1 2 3 3 5
//        3
//        1 2 1
//        2 4 5
//        3 5 3
        Scanner scanner = new Scanner(System.in);
        int numPerson = scanner.nextInt();
        int[] arrInterest = new int[numPerson];
        for(int i = 0; i < numPerson; i++){
            arrInterest[i] = scanner.nextInt();
        }

        int numQuery = scanner.nextInt();
        int[] leftBorder = new int[numQuery];
        int[] rightBorder = new int[numQuery];
        int[] interestQuery = new int[numQuery];
        for(int i = 0; i < numQuery; i++){
            leftBorder[i] = scanner.nextInt();
            rightBorder[i] = scanner.nextInt();
            interestQuery[i] = scanner.nextInt();
        }

        for(int i = 0; i< numQuery; i++){
            int count = 0;
            for(int j = leftBorder[i] - 1; j <= rightBorder[i] - 1; j++){
                if(interestQuery[i] == arrInterest[j])
                    count++;
            }
        System.out.println(count);
        }
    }
}

编辑于 2020-08-14 17:22:12 回复(1)

种田小能手

importbisect

n =int(input())
levels =list(map(int, input().split()))
assertlen(levels) ==n
k2i ={}
fori inrange(n):
    ifnotlevels[i] ink2i:
        k2i[levels[i]] =[i+1]
    else:
        k2i[levels[i]].append(i+1)
# print(k2i)
 
 
q =int(input().strip())
 
for_ inrange(q):
    l, r, k =list(map(int, input().split()))
    ifk notink2i:
        print(0)
        continue
    count =0
    id_l =bisect.bisect_left(k2i[k], l)
    id_r =bisect.bisect_right(k2i[k], r)
    fori inrange(id_l, min(id_r +1, len(k2i[k]))):
        ifl <=k2i[k][i] <=r:
            count +=1
    print(count)

倒排索引字典+二分查找边界

编辑于 2020-08-10 13:10:01 回复(0)

头被锤烂了

if __name__ == "__main__":
    n = int(input())
    if n < 0 and n > 300000:
        print("输入有误")
    like = list(map(int, input().split()))
    q = int(input())
    if q < 0 and q > 300000:
        print("输入有误")
    para = []
    for i in range(q):
        para.append(list(map(int, input().split())))
    for i in range(q):
        l = para[i][0]
        r = para[i][1]
        k = para[i][2]
        ans = 0
        for j in range(l-1, r):
            if like[j] == k:
                ans += 1
        print(ans)

为啥超时了1ms。。。

发表于 2020-03-15 11:56:35 回复(0)

听说海的那边有宝藏

java语言能过吗？50%通过率，题解也是50%通过率

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        ArrayList<String> in=new ArrayList<String>();
        while(s.hasNextLine()){
            in.add(s.nextLine());
        }
        int num=Integer.parseInt(in.get(0));
        String[] people=in.get(1).split(" ");
        String q=in.get(2);
        String[] row;
        int count=0;
        for(int i=3;i<in.size();i++){
            count=0;
            row=in.get(i).split(" ");
            for(int j=Integer.parseInt(row[0])-1;j<Integer.parseInt(row[1]);j++){
                if(row[2].equals(people[j])){
                    count++;
                }
            }
            System.out.println(count);
        }

    }
}

发表于 2019-11-22 16:35:54 回复(0)

zcenao21

import java.util.*;

public class Main {
    public static int binaryFind(UserPre[] sortedListUserPre,int l, int r, int k){
        if(l>r){
            return -1;
        }else if(l==r){
            if(sortedListUserPre[l].prefer==k){
                return l;
            }else{
                return -1;
            }
        }else{
            int m=(l+r)/2;
            if(sortedListUserPre[m].prefer<k){
                l=m+1;
            }
            else if(sortedListUserPre[m].prefer==k){
                return m;
            }
            else{
                r=m-1;
            }
            return binaryFind(sortedListUserPre,l,r,k);
        }
    }

    public static void main(String[] args){
        int userNum;
        int q;

        Scanner sc=new Scanner(System.in);

        //输入用户数
        userNum=sc.nextInt();
        if(userNum<=0||userNum>=300000){
            return;
        }

        //输入用户喜爱值
        UserPre[] prefNums=new UserPre[userNum];
        for(int i=0;i<userNum;i++){
            prefNums[i]=new UserPre(i+1,sc.nextInt());
        }
        Arrays.sort(prefNums,new UserCompare());

        //查询列表
        q=sc.nextInt();
        if(q<=0||q>=300000){
            return;
        }
        Query[] listQuery=new Query[q];
        for(int i=0;i<q;i++){
             Integer[] nums=new Integer[3];
             nums[0]=sc.nextInt();
             nums[1]=sc.nextInt();
             nums[2]=sc.nextInt();

             if(nums[0]<0||nums[0]>userNum||
                nums[1]<0||nums[1]>userNum||
                nums[0]>nums[1]){
                 return;
             }

             listQuery[i]=new Query(nums[0],nums[1],nums[2]);

        }

        //遍历查询列表得到结果
        for(Query query:listQuery){
            int findResult=binaryFind(prefNums,0,userNum-1,query.k);

            //若没找到查询的k值退出
            if(findResult<0){
                return;
            }

            //找到k值的部分,首先往左边找是不是在区间内
            int count=0;
            for(int i=findResult;i>0;i--){
                if(prefNums[i-1].prefer==query.k){
                    if(prefNums[i-1].num>=query.l&&prefNums[i-1].num<=query.r){
                        count++;
                    }
                }else{
                    break;
                }
            }

            //找到k值的部分,再往右边找是不是在区间内
            for(int i=findResult+1;i<=userNum;i++){
                if(prefNums[i-1].prefer==query.k){
                    if(prefNums[i-1].num>=query.l&&prefNums[i-1].num<=query.r){
                        count++;
                    }
                }else{
                    break;
                }
            }

            System.out.println(count);

        }
    }


}

class UserPre{
    int num;
    int prefer;

    UserPre(int num,int prefer){
        this.num=num;
        this.prefer=prefer;
    }
}

class UserCompare implements Comparator<UserPre> {
    @Override
    public int compare(UserPre o1, UserPre o2) {
        return o1.prefer-o2.prefer;
    }
}

class Query{
    int l;
    int r;
    int k;

    Query(int l,int r, int k){
        this.l=l;
        this.r=r;
        this.k=k;
    }
}

始终75%通过，不知道问题在哪，求解答。

发表于 2019-11-03 18:42:32 回复(1)

莫名其妙被删账号

N = int(input())
U = map(int, input().split(' '))
Q = int(input())

T = {}
for idx, val in enumerate(U):
    if val not in T:
        T[val] = 0
    T[val] |= 1<<idx

for i in range(Q):
    L, R, V = map(int, input().split(' '))
    if V not in T:
        print(0)
        continue

    R = (1<<R) - 1
    R ^= (1<<L-1) - 1
    R &= T[V]
    print(bin(R).count('1'))

不知道为啥我这个也显示越界了。。。

发表于 2019-09-05 01:04:24 回复(0)

OFFER_HXJ

import sys
nums = []
try:
    while True:
        c = sys.stdin.readline()
        if c == '':
            break
        nums.append(list(map(int,c.split(' '))))
except:
    pass
 
scores = nums[1]
num = nums[3:]
result = []
if nums[0] == 0:
    print(0)
    break
for i in num:
    tmp = 0
    j = i[0]-1
    while j < i[1]:
        if scores[j] == i[2]:
            tmp+=1
        j+=1
    print(tmp)

自测的时候用给的例子通过了，但是提交运行的时候显示越界了，为什么呢

发表于 2019-08-10 10:00:34 回复(0)

王佳浩

case率 50% 运行超时了... 求指教怎么改进

importjava.util.*;

publicclassMain{

publicstaticvoidmain(String args[]){

Scanner sc = newScanner(System.in);

intn = sc.nextInt();

intarr[] = newint[n];

for(inti =0;i<arr.length;i++){

arr[i]=sc.nextInt();

}

intk = sc.nextInt();

while(k>0){

intl =sc.nextInt();

intr = sc.nextInt();

intp = sc.nextInt();

intsum = 0;

for(inti =l-1;i<=r-1;i++){

if(arr[i]==p){

sum++;

}

System.out.println(sum);

k--;

}

发表于 2019-03-16 09:55:08 回复(0)

Drizzlew

数组越界，不知道为啥，但是测试用例能通过，请各位大佬指教

import sys

n =int(input())

k =input().split(' ')

k =list(map(int, k))

q =int(input())

ql =[[] fori inrange(q)]

fori inrange(q):

temp =input().split()

temp =list(map(int, temp))

ql[i] =temp

flag=True

fori inql:

if(i[0] > len(k)) | (i[1]>len(k)):

flag =False

break

ifflag ==False:

print(error)

else:

forj inql:

t=j

m=t[0:2]

element =[]

fori inrange(m[0],m[1]):

element.append(k[i-1])

#print(element)

count=0

fori inelement:

ifi ==t[-1]:

count =count +1

print(count)

发表于 2019-03-15 20:45:22 回复(1)

孰是孰非201810092110576

//思路是按用户偏好值进行排序，搜索时当偏好值相同且用户编号在查询区间即搜索成功，最后以查询成功的偏好值向用户区间两侧进行
//搜索，统计所有符合要求的用户，C++代码如下：
//提交时间：2019-03-14 语言：C++ 运行时间： 424 ms 占用内存：6620K 状态：答案正确

	#include <iostream>



	#include <vector>



	#include <algorithm>



	using namespace std;  



	struct User



	{



	    int no;



	    int prefer;



	};  



	struct Query



	{



	    int l;



	    int r;



	    int k;



	};



	bool cmp_user(User &a, User &b)



	{



	        return a.prefer < b.prefer;



	}  



	class Solution



	{



	public:



	    void binary(vector<User> & user, Query & q, int & qn, int l, int r)



	    {



	        if(l > r) return;



	        if(l == r)



	        {



	            if(user[l].prefer == q.k)



	            {



	                qn = l;



	            }



	            return;



	        }



	        int m = (l + r)/2;



	        if(user[m].prefer == q.k) {



	            qn = m;



	            return;



	        }



	        if(q.k > user[m].prefer) return binary(user, q, qn, m+1, r);



	        return binary(user, q, qn, l, m-1);



	    }



	    vector<int> fun(vector<User> & user, vector<Query> &query)



	    {



	        int qn, l, r;



	        sort(user.begin(), user.end(), cmp_user);



	        vector<int> res(query.size(), 0);



	        for(int i = 0; i < query.size(); i++)



	        {



	            qn = -1;



	            binary(user, query[i], qn, 0, user.size()-1);



	            if(qn != -1)



	            {



	                for(l = qn; l >= 0 && user[l].prefer == query[i].k; l--)



	                {



	                    if(user[l].no >= query[i].l && user[l].no <= query[i].r) res[i]++;



	                }



	                for(r = qn+1; r < user.size() && user[r].prefer == query[i].k; r++)



	                {



	                     if(user[r].no >= query[i].l && user[r].no <= query[i].r) res[i]++;



	                }



	            }



	        }



	        return res;



	    }



	};



	int main(void)



	{



	    int un, qn;



	    vector<User> user;



	    vector<Query> query;



	    vector<int> res;



	    User x;



	    Query y;



	    cin >> un;



	    for(int i = 0; i < un; i++)



	    {



	        cin >> x.prefer;



	        x.no = i+1;



	        user.push_back(x);



	    }



	    cin >> qn;



	    for(inti = 0; i < qn; i++)



	    {



	        cin >> y.l >> y.r >> y.k;



	        query.push_back(y);



	    }



	    class Solution s;



	    res = s.fun(user, query);



	    for(int i = 0; i < res.size(); i++) cout << res[i] << endl;



	    return 0;



	}

编辑于 2019-03-14 11:33:59 回复(0)

午光

    n =int(input())
    v =list(map(int, input().strip().split()))
    p =int(input())
    fori inrange(p):
        l,r,k =map(int, input().strip().split())
        print(v[l-1:r].count(k))

编辑于 2018-06-11 21:57:12 回复(4)