四大同类基础算法总结：双指针算法思想 / 位运算 / 离散化算法 / 区间合并_双指针算法还有什么

一、双指针算法（时间复杂度 $O(n)$ ）

• 第一类是 双指针分别指向不同的两个序列 ，例如归并排序里合并两个有序子序列的过程。
• 第二类是 双指针指向同一序列 ，例如快速排序中划分区间的过程。
• 一般的写法：

for (int i = 0, j = 0; i < n; i++) {
	while (j < i && check(i, j)) j++;
	// 每道题目的具体逻辑
}
1
2
3
4

• 本质的思想：采用数组的某些性质（一般来说数组具有单调性），把朴素的暴力算法的时间复杂度 $O(n^2)$ 优化到 $O(n)$。
• 一般来讲可以用双指针的算法都能用暴力算法解，但暴力算法可能不满足时间要求，此时需要用双指针算法的思想进行优化。
• 做题步骤：先思考用枚举（暴力）的思想怎么写，然后再寻找 i 和 j 是否存在单调关系，有的话就可以采用双指针的思想优化代码。
• 例题：AcWing 799. 最长连续不重复子序列

#include <iostream>

using namespace std;

const int N = 100010;

int n;
int q[N], s[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    int res = 0;
    for (int i = 0, j = 0; i < n; i ++ )
    {
        s[q[i]] ++ ;
        while (j < i && s[q[i]] > 1) s[q[j ++ ]] -- ;
        res = max(res, i - j + 1);
    }

    cout << res << endl;

    return 0;
}
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

二、位运算常见的两种操作

• 求整数 n 的二进制表示中第 k 位数字：n >> k & 1。
  • 注意：这里的 k 是从个位开始算的，例如 n = 8 = 0b1000，此时第0、1、2位数字均为0，第3位数字为1。
  • 解释：先把第 k 位数字移到最后一位，再查看最后一位即可。
• 返回 n 的最后一位（最低位） 1 ：lowbit(n) = n & -n。
  • 注意：这里返回的是一个二进制数。例如 n = 1010，返回的是10；n = 101000，返回的是1000。
  • 解释：在 C++ 里，一个数的负数的二进制表示是原数二进制取反后加一的结果，因此 n & -n = n & (~n +1)。
  • 举个例子辅助理解：例如 x = 1010…100…0
    • ~x = 0101…011…
    • (~x) + 1 = 0101…100…0
    • 因此 n & (~n +1) = 00…0100…0 = 100…0。
  • 应用：统计一个数里面 1 的个数。思想是，每次找到最后一个 1 的位置，然后把它减掉，统计结果加一，直到该数变成 0 为止。
• 例题：AcWing 801. 二进制中1的个数

#include <iostream>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int x, s = 0;
        scanf("%d", &x);

        for (int i = x; i; i -= i & -i) s ++ ;

        printf("%d ", s);
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 相关题目还有：AcWing 800. 数组元素的目标和、AcWing 2816. 判断子序列 等。

三、离散化（特指整数离散化）

• 对于一个数组 a[n]，一般来讲满足：『$0\le a[i]\le 10^9,0\le n\le 10^5$』（即值域很大，个数较少，所以可以理解成是一个稀疏数组）。离散化的作用在于将数组里面的数做一个映射，最简单的是映射到下标值（或下标加一）：
  
• 离散化步骤：
  • Step 1：数组中可能存在重复元素，因此首先对数组去重。去重采用下面两行代码即可。

  sort(v.begin(), v.end());  // 排序
  v.erase(unique(v.begin(), v.end()), v.end());  // 去重: 将重复元素放在末尾再删除
  1
  2

  • Step 2：采用二分算法算出 x 离散化后的值。二分算法参考博客 【Y总/算法基础课/学习笔记】整数二分和浮点数二分算法（Binary Search）（含算法模板）
  • 补充：由于别的语言没有unique() 函数，因此补充一下unique() 函数的实现。思想是双指针算法，将所有不重复的数放到数组最前面，不重复的数满足两个性质：它是第一个出现的，即 i ≠ 0 以及 a[i] ≠ a[i - 1]。

  vector<int>::iterator unique(vector<int> &v) {
  	int j = 0;
  	for (int i = 0; i < v.size(); i++) 
  		if (!i || v[i] != v[i - 1])
  			v[j++] = v[i];
  	// v[0] ~ v[j - 1] 所有v中不重复的数
  	
  	return v.begin() + j;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9

• 例题：AcWing 802. 区间和
  • 思路：将大值域上的稀疏数组映射到一个小值域上，减少无用数的计算，再采用前缀和计算区间的和即可，直接用前缀和计算量巨大，且存在绝大部分的无用计算。
  • 代码：

  #include <iostream>
  #include <vector>
  #include <algorithm>
  
  using namespace std;
  
  typedef pair<int, int> PII;
  
  const int N = 300010;
  
  int n, m;
  int a[N], s[N];
  
  vector<int> alls;  // 储存所有用到的下标值，范围是30万
  vector<PII> add, query;  // 操作用pair数组存储
  
  // 二分：找到第一个大于等于x的数的下标加一值
  int find(int x)
  {
      int l = 0, r = alls.size() - 1;
      while (l < r)
      {
          int mid = l + r >> 1;
          if (alls[mid] >= x) r = mid;
          else l = mid + 1;
      }
      return r + 1;
  }
  
  int main()
  {
      cin >> n >> m;
      for (int i = 0; i < n; i ++ )
      {
          int x, c;
          cin >> x >> c;
          add.push_back({x, c});
  
          alls.push_back(x);
      }
  
      for (int i = 0; i < m; i ++ )
      {
          int l, r;
          cin >> l >> r;
          query.push_back({l, r});
  
          alls.push_back(l);
          alls.push_back(r);
      }
  
      // 去重
      sort(alls.begin(), alls.end());
      alls.erase(unique(alls.begin(), alls.end()), alls.end());
  
      // 处理插入
      for (auto item : add)
      {
          int x = find(item.first);
          a[x] += item.second;
      }
  
      // 预处理前缀和
      for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i];
  
      // 处理询问
      for (auto item : query)
      {
          int l = find(item.first), r = find(item.second);
          cout << s[r] - s[l - 1] << endl;
      }
  
      return 0;
  }
  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
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74

四、区间合并

• 应用场景：给定多个区间，若区间之间有交集，则进行区间合并，最后输出合并后的区间个数。
• 示例：（合并前的区间为蓝色的，合并后的区间为绿色的，因此答案为 3）
  
• 做法思路：
  • Step 1：按区间左端点排序。
  • Step 2：区间合并。初始化一个边界区间 q 用以维护，再扫描剩余区间 i，此时只会出现三种以下情况
    
    • 区间 i 在维护区间 q 的内部，则 q 无需改变；
    • 区间 i 与维护区间 q 有交集，则 q 需要更新右端点；
    • 区间 i 与维护区间 q 没有任何交集，则 q 无需改变，且可以停止扫描了，因为保证了该维护区间与剩余任何区间都不可能有交集；
  • Step 3：计算合并后区间的数目输出即可。
• 代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

void merge(vector<PII> &segs)
{
    vector<PII> res;
	
	// 区间按左端点排序
    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9;  // 边界区间
    for (auto seg : segs)
        if (ed < seg.first)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);

    if (st != -2e9) res.push_back({st, ed});  // 防止输入区间为空

    segs = res;  // 更新为合并的区间
}

int main()
{
    int n;
    scanf("%d", &n);

    vector<PII> segs;
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        segs.push_back({l, r});
    }

    merge(segs);

    cout << segs.size() << endl;

    return 0;
}
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48