为了不断优化推荐效果,今日头条每天要存储和处理海量数据。假设有这样一种场景:我们对用户按照它们的注册时间先后来标号,对于一类文章,每个用户都有不同的喜好值,我们会想知道某一段时间内注册的用户(标号相连的一批用户)中,有多少用户对这类文章喜好值为k。因为一些特殊的原因,不会出现一个查询的用户区间完全覆盖另一个查询的用户区间(不存在L1<=L2<=R2<=R1)。
为了不断优化推荐效果,今日头条每天要存储和处理海量数据。假设有这样一种场景:我们对用户按照它们的注册时间先后来标号,对于一类文章,每个用户都有不同的喜好值,我们会想知道某一段时间内注册的用户(标号相连的一批用户)中,有多少用户对这类文章喜好值为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的用户的个数
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
// 亲测可用 let print = (_favo, _queryLRK) => { for (let i=0; i<_queryLRK.length; i++) { let [l, r, k] = _queryLRK[i]; let fk = _favo[k]; let count = 0; if (fk === undefined) { console.log(0); } else { for (let j=0; j<fk.length; j++) { if (l <= fk[j] && fk[j] <= r) { count ++; } } console.log(count); } } } let readline = require('readline'); let rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); let n; let count = 0; let favo = {}; let q; let queryLRK = []; rl.on('line', (line) => { let tokens = line.split(' '); if (count === 0) { n = parseInt(tokens[0]); } else if (count === 1) { for (let i=0; i<n; i++) { if (favo[tokens[i]] === undefined) { favo[tokens[i]] = []; } favo[tokens[i]].push(i+1); } } else if (count === 2) { q = parseInt(tokens[0]); } else { queryLRK.push(tokens); q--; if (q === 0) { print(favo, queryLRK); rl.close(); } } count < 3 && count++; });
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); HashMap<Integer,ArrayList<Integer>> map = new HashMap<>(); for(int i=0;i<n;i++){ int like=sc.nextInt(); if(map.containsKey(like)){ map.get(like).add(i+1); }else{ ArrayList<Integer> users = new ArrayList<>(); users.add(i+1); map.put(like,users); } } int m = sc.nextInt(); while(m>0){ int left=sc.nextInt(); int right=sc.nextInt(); int k=sc.nextInt(); int res = 0; if(map.containsKey(k)){ ArrayList<Integer> list = map.get(k); for(int i=0;i<list.size();i++){ if(list.get(i)>=left&&list.get(i)<=right){ res++; } } } System.out.println(res); m--; } } }
补记一下这个题目 首先看到的就是数据范围 这么大的数据范围的区间查询 肯定需要nlogn的 时间复杂度来完成 将所有数值按照数的值将下标顺序的存储在vector里面 按照输入的k值查找 到相应的vector 再在这个vector里面对l和r进行二分查找得到具体答案值 #include <bits/stdc++.h> using namespace std; const int maxn = 3e5 + 10; struct node { int val; int idx; }a[maxn]; bool cmp(node x,node y) { if(x.val != y.val) return x.val < y.val; return x.idx < y.idx; } vector<int> tmp[maxn]; int tot = 0,f[maxn]; int main() { int n;scanf("%d",&n); for(int i = 1; i <= n; i++) { scanf("%d",&a[i].val); a[i].idx = i; } sort(a + 1,a + 1 + n,cmp); for(int i = 1; i <= n; i++) { int j = i; f[++tot] = a[i].val; while(a[j].val == a[i].val && j <= n) { tmp[tot].push_back(a[j].idx); j++; } i = j - 1; } int q; cin>>q; //for(int i = 1; i <= tot; i++) printf("%d ",f[i]); //puts(""); //puts(""); while(q--) { int l,r,k; scanf("%d%d%d",&l,&r,&k); int pos = lower_bound(f + 1,f + tot + 1,k) - (f); //printf("%d %d \n",pos,f[pos]); if(f[pos] != k) { puts("0");continue; } else { //printf(" r = %d\n",upper_bound(tmp[pos].begin(),tmp[pos].end(),r) - tmp[pos].begin()); int r1 = upper_bound(tmp[pos].begin(),tmp[pos].end(),r) - tmp[pos].begin(); int l1 = lower_bound(tmp[pos].begin(),tmp[pos].end(),l) - tmp[pos].begin(); printf("%d\n",r1 - l1); //printf("l = %d r = %d\n",l1,r1); //printf(" l = %d\n",upper_bound(tmp[pos].begin(),tmp[pos].end(),l) - tmp[pos].begin()); } } return 0; }
let readline = require('readline') const rl = readline.createInterface({ input: process.stdin, output: process.stdout }) let n = -3 let k = 0 let like = [] let q = 0 let query = [] let ans = [] rl.on('line', function(line){ if (n === -3) { k = parseInt(line.trim()) n++ } else if (n === -2) { like = line.trim().split(' ').map(item => parseInt(item)) n++ } else if (n === -1) { q = parseInt(line.trim()) n++ } else { query.push(line.trim().split(' ').map(item => parseInt(item))) n++ } if (n === q) { ans = userlike(like, q, query) for (let i = 0; i < ans.length; i++) { console.log(ans[i]) } n = -3 k = 0 like = [] q = 0 query = [] ans = [] } }) function userlike(like, q, query) { let ans = [] let l = 0 let r = 0 let k = 0 let hash = {} for (let i = 0, len = like.length; i < len; i++) { if (!hash[like[i]]) { hash[like[i]] = [i] } else { hash[like[i]].push(i) } } for (let i = 0; i < q; i++) { l = query[i][0]-1 r = query[i][1]-1 k = query[i][2] ans[i] = 0 if (hash[k]) { let temp = hash[k] for (let j = 0; j < temp.length; j++) { if (temp[j] >= l && temp[j] <= r) { ans[i]++ } } } } return ans }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | #include<stdio.h> intmain() { intn,q; scanf("%d",&n); inta[n]; for(inti=0;i<n;i++){ scanf("%d",&a[i]); } scanf("%d",&q); intb[q][3]; for(inti=0;i<q;i++){ scanf("%d",&b[i][0]); scanf("%d",&b[i][1]); scanf("%d",&b[i][2]); } for(inti=0;i<q-1;i++){ intcount=0; for(intj=b[i][0]-1;j<=b[i][1]-1;j++){ if(b[i][2]==a[j]) count++; } printf("%d\n",count); } intcount=0; for(inti=b[q-1][0]-1;i<=b[q-1][1]-1;i++){ if(b[q-1][2]==a[i]) count++; } printf("%d",count); } |
import java.util.*; public class Main{ public int getCount(List<Integer> data, int target){ int left=0, right = data.size()-1, middle=0; while(left <= right){ middle = left + (right-left)/2; if (data.get(middle) > target) right = middle-1; else if(data.get(middle) < target) left = middle+1; else return middle; } return left; } public void f(){ Scanner sc = new Scanner(System.in); while(sc.hasNextLine()){ int n, q, l, r, k; n = Integer.parseInt(sc.nextLine()); Map<Integer, List<Integer>> map = new HashMap<>(); for(int i=1; i<=n; i++) { int worth = sc.nextInt(); if(!map.containsKey(worth)) map.put(worth, new ArrayList<>()); map.get(worth).add(i); } sc.nextLine(); q = Integer.parseInt(sc.nextLine()); for(int i=0; i<q; i++){ l = sc.nextInt(); r = sc.nextInt(); k = sc.nextInt(); sc.nextLine(); if(map.containsKey(k)){ if(r<map.get(k).get(0) || l > map.get(k).get(map.get(k).size() -1)) System.out.println(0); else{ int left = getCount(map.get(k), l); int right = getCount(map.get(k), r); if (right < map.get(k).size() && map.get(k).get(right) == r) System.out.println(right-left+1); else System.out.println(right - left); } }else System.out.println(0); } } } public static void main(String[] args){ new Main().f(); } }
//给前面的回答添加了点注释,方便阅读 let chaxunzuarr = []; //第一行输入,用户个数 let yonghushu = readline(), //第二行输入,用户对应喜好,转化为数组 xihaoduarr = readline().split(' '), //第三行输入,查询组数 chaxunzushu = readline(); //循环所有查询组,4行开始的所有行 for(let i = 0;i<chaxunzushu;i++){ //取得每行值,转为数组 chaxunzuarr[i] = readline().split(' '); } let arr = []; //遍历喜好度数组,将相同喜好度的下标添加进一个新数组 //样例添加完后生成arr=[,[0],[1],[2,3],,[4]] xihaoduarr.forEach((item,index) => { if(arr[item] == undefined){ arr[item] = []; } arr[item].push(index); }); //遍历查询组 for(let j = 0;j<chaxunzushu;j++){ //取得每行第一个数l,转化为下标-1 let start = chaxunzuarr[j][0] - 1, //取得每行第二个数r,转化为下标-1 end = chaxunzuarr[j][1] - 1, //取得每行第三个数k,喜好度 value = chaxunzuarr[j][2], //初始化结果用户个数 geshu = 0; if(arr[value] == undefined){ //下标数组为未定义时,无喜好度 console.log(0); }else{ //循环下标数组内元素,判断元素数组内元素是否处于标号间 arr[value].forEach(e=>{ if(e>=start && e<=end){ geshu++; } }) print(geshu); } }
牛客网对js代码测试充满了深深地恶意。 function res(people,likesArr,q,selectObj){ for(let i = 0; i < q; i++){ let bef = selectObj[i][0];// 1 2 1 let aft = selectObj[i][1];// 2 let c = selectObj[i][2]; let com = likesArr.slice(bef-1, aft-1); let num = 0; if(com.length > 0){ for(let j = 0; j < com.length; j++){ if(com[j] === c){ num++; } } } console.log(num); } } res(5,[1,2,3,3,5],3,[[1,2,1],[2,4,5],[3,5,3]]);
不吹不黑,这题我做了至少5个小时。 JS代码如下:let chaxunzuarr = [];
#include<iostream> #include<unordered_map> #include<vector> using namespace std; int main(){ int n = 0; cin>>n; unordered_map<int,vector<int>> fav_users; for(int i = 0;i<n;i++){ int fav = 0; cin>>fav; if(fav_users.count(fav)){ fav_users[fav].push_back(i+1); }else{ fav_users[fav] = {i+1}; } } int rows = 0; cin>>rows; vector<int> result(rows); for(int i = 0;i<rows;i++){ int start = 0, end = 0, fav = 0, count = 0; cin>>start>>end>>fav; for(int x:fav_users[fav]){ if(x>=start && x<=end) count++; if(x>end)break; } result[i] = count; } for(int x:result){ cout<<x<<endl; } return 0; }
C++, 使用哈希表记录每个喜好值对应的下标集合,然后二分查找。
#include <bits/stdc++.h> using namespace std; int main() { int n, like;; cin >> n; unordered_map<int, vector<int>> mp; for (int i = 1; i <= n; ++i) { scanf("%d", &like); mp[like].push_back(i); } int q, left, right; cin >> q; while (q--) { scanf("%d%d%d", &left, &right, &like); auto it1 = lower_bound(mp[like].begin(), mp[like].end(), left); auto it2 = upper_bound(mp[like].begin(), mp[like].end(), right); cout << (it2 - it1) << endl; } return 0; }
const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; void async function () { // Write your code here let idx = 0; let userStar = {}; while(line = await readline()){ let tokens = line.split(' '); if (idx === 1) { userStar = tokens.reduce((pre, cur, idx) => { if (pre[cur]) { pre[cur].push(idx) return pre; }; pre[cur] = [idx]; return pre; }, {}); } if (idx > 2) { const start = parseInt(tokens[0]) - 1; const end = parseInt(tokens[1]) - 1; const starList = userStar[tokens[2]] ?? []; console.log(starList.filter(v => v >= start && v <= end).length) } idx++ } }()
let usernum=readline(); let user=readline().split('') var arr=[] for(var i=0;i<=user.length;i++){ if(i%2==0){ arr.push(user[i]) }else{ continue } } let q=readline() var fun=function(s,f,k){ let num=0; for(var i=s-1;i<f;i++){ if(arr[i]==k){ num++; continue }else{ continue } } print(num) } while(lines=readline()){ var liness = lines.split(''); var s = parseInt(liness[0]); var f = parseInt(liness[2]); var k = parseInt(liness[4]); fun(s,f,k); }
let l1=readline(); let n1=parseInt(l1); let l2=readline(); let yhxh=l2.split(' ').map((i)=>parseInt(i)); let yhxharr=[]; yhxh.forEach((item,i)=>{ if(yhxharr[item]==undefined) yhxharr[item]=[]; yhxharr[item].push(i); }) let l3=readline(); let n3=parseInt(l3);//测试数据个数 for(let i=0;i<n3;i++){ let lines=readline(); let cesz=lines.split(' ').map((i)=>parseInt(i)); let l=cesz[0]-1; let r=cesz[1]-1; let k=cesz[2]; let cnt=0; if(yhxharr[k]==undefined) print(0); else{ yhxharr[k].forEach((item,i)=>{ if(item>=l&&item<=r) cnt++; }) print(cnt); } }
/** * 不知道哪个活雷锋在第15个测试用例里给了个不存在的k,真的是吃了屎。直接到find函数里面加上一个判断吧 * 如果用传统的线性查找的方法应该会超时 * 提高速度,可以用hashmap的查找和二分查找,能用二分查找是因为id是递增有序的 * 把具有相同k值的用户编号用arraylist存储,k和arraylist构成hashmap, * 这样一来,k值的查询可以用O(1)的时间 * 然后获得具有相同k值的用户id列表,用二分查找,注意查找的时候是分左右边界的,给我的l和r不一定在列表里面 * 如果找不到l,那就返回l后面一个,如果找不到r,就返回r前面一个,做个差就是在[l,r]内的个数了 */ import java.io.IOException; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) throws IOException{ List<Integer> likes = new ArrayList<>(); HashMap<Integer,List<Integer>> k_to_likes = new HashMap<>(); Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for (int i = 0; i < n; i++) { likes.add(sc.nextInt()); int index = likes.get(i); if (! k_to_likes.containsKey(index)){ List<Integer> item = new ArrayList<>(); k_to_likes.put(index, item); } k_to_likes.get(index).add(i+1); } int p = sc.nextInt(); for (int i = 0; i < p; i++) { int l = sc.nextInt(); int r = sc.nextInt(); int k = sc.nextInt(); find(k_to_likes, l, r, k); } // while (sc.hasNextInt() && ) } public static void find(HashMap<Integer,List<Integer>> k_to_likes, int l, int r, int k) throws IOException { if (! k_to_likes.containsKey(k)) { System.out.println(0); return; } List<Integer> sanme_like = k_to_likes.get(k); int count = binary_seatch(sanme_like,r,"right")-binary_seatch(sanme_like,l,"left") + 1; System.out.println(count); } public static int binary_seatch(List<Integer> sanme_like, int target, String position) throws IOException{ if (sanme_like.isEmpty()) return 0; int left = 0, right = sanme_like.size() -1; while (left <= right) { int mid = left + (right-left)/2; if (sanme_like.get(mid) == target) return mid; else if (sanme_like.get(mid) > target) { right = mid - 1; } else if (sanme_like.get(mid) < target) { left = mid + 1; } } return position.equals("left") ? left : right; } }
let readline = require('readline'); let lines = 1; let n; let arr = [] let favo = {} let t; let query = [] // var k=2; //这里代表题目中设定好的输入的行数 let rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); rl.on('line', (line) => { if (lines === 1) { n = line-0; } if (lines === 2) { arr = line.split(' ') for (let i = 0; i < n; i++){ if (!favo[arr[i]]) { favo[arr[i]] =[] } favo[arr[i]].push(i+1) } } else if (lines === 3) { t = line - 0; } else if(lines>3){ query.push(line.split(' ')); if (query.length === t) { request(favo,query); rl.close(); } } lines++; }) function request(_favo, _query) { for (let i = 0; i < _query.length; i++) { let [l, r, k] = _query[i]; let count = 0; if (!_favo[k]) { // console.log(_favo[k]) console.log(0); } else { for (let j = 0; j < _favo[k].length; j++){ if (favo[k][j] >= l && favo[k][j] <= r ) count++; } console.log(count); } } }
const n = readline(); const preferArr = readline().split(' ').map(item => parseInt(item)); // 喜好数组 preferArr.unshift(-1); // 在数组头部插入一个元素,对其下标 const amount = parseInt(readline()); // 查询数组 const hash = new Map(); // 构造哈希表 preferArr.forEach((item, index) => { if (!hash.has(item)) { hash.set(item, [index]) } else { const temp = hash.get(item); temp.push(index); hash.set(item, temp); } }) for (let i = 0; i < amount; i++) { let cnt = 0; const data = readline().split(' ').map(item => parseInt(item)); const l = data[0]; const r = data[1]; const k = data[2]; if (hash.has(k)) { const idList = hash.get(k); if (r < idList[0] || l > idList[idList.length - 1]) { console.log(cnt); } else { // 二分查找获取哈希表对应项中的下标 const left = getIndex(idList, l); const right = getIndex(idList, r); console.log(left, right); if (right < idList.length && idList[right] === r) { console.log(right - left + 1); } else { console.log(right - left); } } } else { console.log(0); } } function getIndex(arr, target) { let l = 0, r = arr.length - 1; while (l <= r) { let mid = Math.floor((l + r) / 2); if (arr[mid] === target) { return mid; } else if (arr[mid] < target) { l = mid + 1; } else { r = mid - 1; } } return l; }