原文链接: https://leetcode-cn.com/problems/rank-from-stream-lcci

英文原文

Imagine you are reading in a stream of integers. Periodically, you wish to be able to look up the rank of a number x (the number of values less than or equal to x). lmplement the data structures and algorithms to support these operations. That is, implement the method track (int x), which is called when each number is generated, and the method getRankOfNumber(int x), which returns the number of values less than or equal to x.

Note: This problem is slightly different from the original one in the book.

Example:

Input:
["StreamRank", "getRankOfNumber", "track", "getRankOfNumber"]
[[], [1], [0], [0]]
Output:
[null,0,null,1]

Note:

• x <= 50000
• The number of calls of both track and getRankOfNumber methods are less than or equal to 2000.

中文题目

假设你正在读取一串整数。每隔一段时间，你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作，也就是说：

实现 track(int x) 方法，每读入一个数字都会调用该方法；

实现 getRankOfNumber(int x) 方法，返回小于或等于 x 的值的个数。

注意：本题相对原题稍作改动

示例:

输入:
["StreamRank", "getRankOfNumber", "track", "getRankOfNumber"]
[[], [1], [0], [0]]
输出:
[null,0,null,1]

提示：

• x <= 50000
• track 和 getRankOfNumber 方法的调用次数均不超过 2000 次

通过代码

高赞题解

思路

主要就是使用二分查找找到相应下标。

代码

class StreamRank {
    private ArrayList<Integer> list;

    public StreamRank() {
        list = new ArrayList<>(50000);
    }

    public void track(int x) {
        int idx = Collections.binarySearch(list, x);
        if (idx < 0) idx = -idx - 1;
        list.add(idx, x);
    }

    public int getRankOfNumber(int x) {
        int idx = Collections.binarySearch(list, x);
        if (idx < 0) idx = -idx - 1;
        while (idx < list.size() && list.get(idx) <= x)
            ++idx;
        return idx;
    }
}

统计信息

通过次数	提交次数	AC比率
5161	8268	62.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言