为了不断优化推荐效果,今日头条每天要存储和处理海量数据。假设有这样一种场景:我们对用户按照它们的注册时间先后来标号,对于一类文章,每个用户都有不同的喜好值,我们会想知道某一段时间内注册的用户(标号相连的一批用户)中,有多少用户对这类文章喜好值为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
import java.util.*; public class Main{ public static void main(String[] args){ Scanner input = new Scanner(System.in); int num = input.nextInt(); Map<Integer, List<Integer>> map = new HashMap<>(); for(int i = 0; i < num; i++){ int score = input.nextInt(); if(!map.containsKey(score)){ List<Integer> list = new ArrayList<>(); list.add(i+1); map.put(score, list); }else{ List<Integer> list = map.get(score); list.add(i+1); } } int time = input.nextInt(); for(int i = 0; i < time; i++){ int count = 0; int left = input.nextInt(); int right = input.nextInt(); int target = input.nextInt(); List<Integer> list = map.get(target); if(list != null){ int length = list.size(); for(int j = 0; j < length; j++){ int a = list.get(j); if((a >= left) && (a <= right)){ count++; } } } System.out.println(count); } } }
import java.util.Scanner; public class Main { //查找某个区间对文章的喜爱度为k的人个数 static int getNum(int[] usr_like, int l, int r, int k) { int count = 0; for (int i = l; i <= r; i++) { if(usr_like[i]==k) count++; } return count; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] usr_like = new int[n]; for (int i = 0; i < n; i++) { usr_like[i] = sc.nextInt(); } int q = sc.nextInt(); while (q-- != 0) { int l = sc.nextInt(); int r = sc.nextInt(); int k = sc.nextInt(); int ret = getNum(usr_like,l-1,r-1,k); System.out.println(ret); } } }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner in=new Scanner(System.in); int n=in.nextInt(); Map<Integer,ArrayList<Integer>> perfer=new HashMap<>(); for(int i=1;i<n+1;i++){ int per=in.nextInt(); if(perfer.containsKey(per)){ ArrayList<Integer> list=perfer.get(per); list.add(i); } else{ ArrayList<Integer> list=new ArrayList<>(); list.add(i); perfer.put(per,list); } } int sel=in.nextInt(); for(int i=0;i<sel;i++){ int count=0; int start=in.nextInt(); int stop=in.nextInt(); int per=in.nextInt(); if(perfer.containsKey(per)){ ArrayList<Integer> li=perfer.get(per); Iterator<Integer> ltr=li.iterator(); while(ltr.hasNext()){ int num=ltr.next(); if(num>=start&&num<=stop){ count++; } } } System.out.println(count); } } }
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int user = sc.nextInt(); Map<Integer, List<Integer>> map = new HashMap<>(); for (int i = 1; i <= user; i++) { int fav = sc.nextInt(); if (!map.containsKey(fav)) { List<Integer> list = new ArrayList<>(); list.add(i); map.put(fav, list); } else { List<Integer> list = map.get(fav); list.add(i); } } int group = sc.nextInt(); for (int i = 0; i < group; i++) { int a = sc.nextInt(); int b = sc.nextInt(); int k = sc.nextInt(); int sum = 0; List<Integer> list = map.get(k); if (list != null) { for (int j = 0; j < list.size(); j++) { if (list.get(j)>=a&&list.get(j)<=b) { sum++; } } } System.out.println(sum); } } }
import java.util.*; public class Main { Map<Integer, List<Integer>> map = new HashMap<>(); void solution() { Scanner sc = new Scanner(System.in); int n, q, l, r, k, x; n = sc.nextInt(); for (int i = 1; i <= n; i++) { x = sc.nextInt(); if (!map.containsKey(x)) { map.put(x, new ArrayList<>()); } map.get(x).add(i); } q = sc.nextInt(); for (int i = 0; i < q; i++) { l = sc.nextInt(); r = sc.nextInt(); k = sc.nextInt(); List<Integer> indexList = map.getOrDefault(k, null); if (indexList == null) { System.out.println(0); } else { System.out.println(help(indexList, l, r)); } } } private int help(List<Integer> indexList, int l, int r) { int left = upper(indexList, l); int right = lower(indexList, r); if (left < 0 || right >= indexList.size()) { return 0; } return right - left + 1; } private int lower(List<Integer> indexList, int key) { int low = 0, hi = indexList.size()-1; while (low <= hi) { int mid = (low + hi) / 2; if (indexList.get(mid) <= key) { low = mid + 1; } else { hi = mid - 1; } } return low - 1; } private int upper(List<Integer> indexList, int key) { int low = 0, hi = indexList.size()-1; while (low <= hi) { int mid = (low + hi) / 2; if (indexList.get(mid) < key) { low = mid + 1; } else { hi = mid - 1; } } return hi + 1; } public static void main(String[] args) { new Main().solution(); } }
// 在第1,2位作者的基础上优化:索引值大于r-1之后可以break跳出循环 public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); Map<Integer, List<Integer>> likeMap = new HashMap<>(); for (int i = 0; i < n; i++) { int likeCount = scanner.nextInt(); if (likeMap.containsKey(likeCount)) { likeMap.get(likeCount).add(i); } else { ArrayList<Integer> list = new ArrayList<>(); list.add(i); likeMap.put(likeCount, list); } } int q = scanner.nextInt(); int[] result = new int[q]; for (int i = 0; i < q; i++) { int l = scanner.nextInt(); int r = scanner.nextInt(); int k = scanner.nextInt(); List<Integer> ls = likeMap.get(k); if (ls == null) { result[i] = 0; continue; } Iterator<Integer> iterator = ls.iterator(); int re = 0; while (iterator.hasNext()) { Integer next = iterator.next(); if (next < l - 1) { continue; } if (next < r) { re++; } else { break; } } result[i] = re; } for (int i = 0; i < q; i++) { System.out.println(result[i]); } }
n = int(input().strip()) like = [int(x) for x in input().strip().split()] hashmap = {} for i in range(n): if like[i] not in hashmap: hashmap[like[i]] = [i+1] else: hashmap[like[i]].append(i+1) q = int(input().strip()) for _ in range(q): a,b,k = map(int, input().strip().split()) count = 0 if k in hashmap: for x in hashmap[k]: if x >= a and x <= b: count += 1 print(count)
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int peoplenum = sc.nextInt(); Map<Integer, List<Integer>> map = new HashMap<>(); /** * 输入的时候会出现不同的用户数会出现相同的关注度 * 所以map这样可以自动分出不同关注度分别又多少关注度 */ for (int i = 1; i <= peoplenum; i++) { int guanzhudu = sc.nextInt(); if (!map.containsKey(guanzhudu)) { List<Integer> list = new ArrayList<>(); list.add(i); map.put(guanzhudu, list); } else { List<Integer> list = map.get(guanzhudu); list.add(i); } } int num = sc.nextInt();//查询组数 // List<chaxun> list=new ArrayList<>(); // for (int i=0;i<num;i++){ // list.add(new chaxun(sc.nextInt(),sc.nextInt(),sc.nextInt())); // } // for (int i=0;i<num;i++){ // int c=Fun(list,i,map); // System.out.println(c); // } /** * 定义一个查找关注度的循环 * 找到要查找关注度的哪个小组 * 小组中的用户大小要与输入的匹配 */ for (int i = 0; i < num; i++) { int a = sc.nextInt(); int b = sc.nextInt(); int key = sc.nextInt(); int sum = 0; List<Integer> list = map.get(key); if (list!=null){ for (int k = 0; k < list.size(); k++) { if (list.get(k) >= a && list.get(k) <= b) { sum += 1; } } } System.out.println(sum); } }
#include<iostream> #include<algorithm> #include<vector> #include<string> #include<map> using namespace std; int main() { int n,q,x; cin >> n; map<int, vector<int>> map; for (int i = 1; i <= n; i++) { cin >> x; map[x].push_back(i); } cin >> q; int l, r, k; for (int i = 0; i < q; i++) { cin >> l >> r >> k; int cnt = 0; vector<int> list = map[k]; for (int j = 0; j < list.size(); j++) { if (list[j] <= r && list[j] >= l) cnt++; } cout << cnt << endl; } system("pause"); }