网易笔试-人数统计(二分查找)

目录

1. 输入描述
2. 输出描述
3. 样例

题目描述

小易的公司一共有 n 名员工，第 i 个人每个月的薪酬是 x_i 万元。

现在效益的老边向小易提了 m 次询问，每次询问老板都会给出一个整数 k，小易要快速回答老板工资等于 k 的员工的数量。

输入描述

第一行，两个空格间隔的整数 n 和 m，表示人数和提问的次数
第二行，n 个空格间隔的整数 x_i，表示每个员工的薪酬
接下来有 m 行，每一行一个整数，表示老板的一次提问。

1 <= m <= 80000，1 <= n <= 100000， 1 <= x_i <= 500,000,000

输出描述

m 行，每行一个整数，表示对应提问的答案

样例

输入1

7 4
6 2 1 2 6 2 5
6
5
8
2

AC 代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private static int [][]x;
    private static int id;
    private static int query(int q) {
        if (id == 0) return 0;
        int l = 0, h = id - 1;
        int m;
        if (q < x[l][0] || q > x[h][0]) return 0;
        while (l < h) {
            m = (l + h) / 2;
            if (x[m][0] > q)
                h = m-1;
            else if(x[m][0] < q)
                l = m+1;
            else
                return x[m][1];
        }
        if (x[l][0] == q) return x[l][1];
        return 0;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int []cm = new int[n];
        x = new int[n][2];
        for (int i = 0; i < n; i++) {
            cm[i] = sc.nextInt();
        }
        Arrays.sort(cm, 0, n);
        int cur = cm[0], cur_i = 0;
        id = 0;
        for (int i = 1; i < n; i++) {
            while (i < n && cm[i] == cur) {
                i++;
            }
            x[id][0] = cur;
            x[id][1] = i - cur_i;
            if (i < n) cur = cm[i];
            cur_i = i;
            id++;
        }
        for (int i = 0; i < m; i++) {
            int q = sc.nextInt();
            System.out.println(query(q));
        }
    }
}