TB椰程 TypeBuddy 打字搭子

双指针

CSP-J · 编程模板 · 片段 · cpp · 难度 3/5 · 共 409 字

两下标协同推进，常把 O(n^2) 降到 O(n)

  • 算法
  • 双指针

前置内容

正文

// 双指针：两下标协同推进
// 常用于有序数组 / 区间问题
// 把 O(n^2) 降到 O(n)
// 例：有序数组去重（保留一个）
#include <cstdio>
int n, a[100005], m = 0;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    // i 慢指针，j 快指针
    for (int j = 1; j <= n; j++) {
        // 遇到不同才保留
        if (a[j] != a[m]) {
            a[++m] = a[j];
        }
    }
    // m 即为去重后长度
    printf("%d\n", m);
    return 0;
}

CSP-J · 编程模板的其它内容

打字首页 · 词库画廊 · 编程打字 · 指法入门 · 天梯榜 · 数据分析 · 班级课堂 · 关于我们
椰程 TypeBuddy 打字搭子 —— 键盘指法练习 · 单词记忆 · 班级课堂 · 在线 PK