LeetCode 933. 最近的请求次数

思路

二分查找O(nlog(n)) n<=1e4;

代码

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
class RecentCounter {
public:
    static const int N=1e4+1;
    int a[N];
    int len=0;
    RecentCounter() {

    }
    int binary_search(int l,int r,int m){
        if(l>r) return l;
        int mid=(l+r)/2;
        if(a[mid]==m) return mid;
        if(a[mid]>m) return binary_search(l,mid-1,m);
        else return binary_search(mid+1,r,m);
        //return 0;
    }
    int ping(int t) {
        a[len]=t;
        int res=len-binary_search(0,len,t-3000)+1;
        len++;
        return res;
    }
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter* obj = new RecentCounter();
 * int param_1 = obj->ping(t);
 */

参考

  1. https://leetcode-cn.com/problems/number-of-recent-calls/ ↩