为了不断优化推荐效果,今日头条每天要存储和处理海量数据。假设有这样一种场景:我们对用户按照它们的注册时间先后来标号,对于一类文章,每个用户都有不同的喜好值,我们会想知道某一段时间内注册的用户(标号相连的一批用户)中,有多少用户对这类文章喜好值为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
/** * 不知道哪个活雷锋在第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; } }
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
outPut();
}
public static void outPut() {
Scanner sc = new Scanner(System.in);
int userNum = 5;
userNum = sc.nextInt();
int[] likeNum =new int[userNum];
for (int n = 0; n < userNum; n++) {
likeNum[n]=sc.nextInt();
}
int list = 0;
list = sc.nextInt();
int[][] select =new int[list][3];// {{1, 2, 1}, {2, 4, 5}, {3, 5, 3}};
int count = 0;
for (int k = 0; k < list; k++) {
select[k][0] = sc.nextInt();
select[k][1] = sc.nextInt();
select[k][2] = sc.nextInt();
}
for (int[] aSelect : select) {
for (int m = aSelect[0] - 1; m < aSelect[1]; m++) {
if (likeNum[m] == aSelect[2])
count++;
}
System.out.println(count);
count = 0;
}
}
}
顺序查找,超时,只通过了50%的case
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(); } }