关于算法:双指针算法模板及练习

文章和代码曾经归档至【Github 仓库：algorithms-notes】或者公众号【AIShareLab】回复 算法笔记 也可获取。

日志统计

小明保护着一个程序员论坛。当初他收集了一份”点赞”日志，日志共有 N 行。

其中每一行的格局是：

ts id

示意在 ts 时刻编号 id 的帖子收到一个”赞”。

当初小明想统计有哪些帖子已经是”热帖”。

如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞，小明就认为这个帖子曾是”热帖”。

具体来说，如果存在某个时刻 T 满足该帖在 [T,T+D) 这段时间内 (留神是左闭右开区间) 收到不少于 K 个赞，该帖就曾是”热帖”。

给定日志，请你帮忙小明统计出所有曾是”热帖”的帖子编号。

输出格局

第一行蕴含三个整数 N,D,K。

以下 N 行每行一条日志，蕴含两个整数 ts 和 id。

输入格局

按从小到大的程序输入热帖 id。

每个 id 占一行。

数据范畴

$1≤K≤N≤10^5$,
$0≤ts,id≤10^5,$
$1≤D≤10000$

输出样例：

7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3

输入样例：

1
3

个别做法

for(time) // 遍历所有的时间段
{memset(cnt, 0, sizeof cnt);
    for (id) // 遍历所有的帖子
    {cnt[id] ++ ; // 统计次数
        if(cnt[id] >= k) st[id] = true;
    }
}

for(int i = 1; i <= 100000; i ++)
{if(st[i]) cout << i <<endl;
}

用双指针算法改良

每次只须要变动 i（首）和 j（尾）即可，两头的局部没有变动。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

using namespace std;

// 此题须要对二元组进行排序，须要针对工夫和 id 进行排序。// 能够用 pair 来 sort 排序，默认是以 first 为第一关键字，second 为第二关键字排序
typedef pair<int, int> PII;

const int N = 100010;

int n, d, k;
PII logs[N];
int cnt[N];  // 用来记录某 id 号取得的赞数，示意模式为 cnt[id]++;
bool st[N];  // 记录每个帖子是否是热帖, 因为 id <= 1e5，所以能够利用遍从来输入。int main()
{scanf("%d%d%d", &n, &d, &k);
    for (int i = 0; i < n; i ++) scanf("%d%d", &logs[i].x, &logs[i].y);

    // 对 pair 进行排序, 排序时默认以 first 为准排序
    sort(logs, logs + n);
    // 双指针算法，i 在前，j 在后
    for (int i = 0, j = 0; i < n; i ++)
    {int id = logs[i].y; // 把每个获赞的帖子 id 存入 id
        cnt[id] ++ ; // 取得一个赞，所以此刻 ++；while (logs[i].x - logs[j].x >= d) // 如果俩个帖子工夫相差超过 d，阐明该赞有效
        {cnt[logs[j].y] -- ; // 所以此刻 --；j ++ ; // 要把指针 j 往后，否则死循环
        }

        if (cnt[id] >= k) st[id] = true;  // 如果该 id 贴赞超过 k，阐明是热帖
    }

    for (int i = 0; i <= 100000; i ++) // 循环输入热帖
        if (st[i])
            printf("%d\n", i);

    return 0;
}