离散化

知识点

离散化就是将无穷大集合中的若干个元素映射为有限集合以便于统计。
通常表现为取值范围非常大，但是数目比较有限，并且不关心数值的绝对大小（只把数值作为代表，或者只和它们的相对顺序有关），此时就可以把m个数映射为1~m，这样一来，时间、空间复杂度降至与m有关。

模板

  1. // C++ STL写法
  2. void discrete() {
  3.     vector<int> alls; // 存储所有待离散化的值
  4.     sort(alls.begin(), alls.end()); // 将所有值排序
  5.     alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素
  6. }
  8. // 二分求出x对应的离散化的值
  9. int find(int x) // 找到第一个大于等于x的位置
  10. {
  11.     int l = 0, r = m - 1;
  12.     while (l < r)
  13.     {
  14.         int mid = l + r >> 1;
  15.         if (alls[mid] >= x) r = mid;
  16.         else l = mid + 1;
  17.     }
  18.     return r + 1; // 映射到1, 2, ...n
  19. }
  21. // 通用写法
  22. void discrete() {
  23.     sort(alls + 1, alls + n + 1);
  24.     for (int i = 1; i <= n; i++)
  25.         if (i == 1 || alls[i] != alls[i - 1])
  26.             alls[m++] = alls[i];
  27. }
  29. int query(int x) {    // 或者像上面一样写一个二分
  30.     return lower_bound(alls, alls + m, x) - alls + 1;
  31. }

习题

电影

如果只是用于计数的话，离散化没什么必要，直接用哈希表就好了，本质上是一样的

  1. // 离散化
  2. #include <iostream>
  3. #include <algorithm>
  5. using namespace std;
  7. const int N = 2e5 + 10;
  9. int n, m, cnt, dcnt;
  10. int a[N], b[N], c[N], all[3*N], dis[3*N], sum[3*N];
  12. void discrete() {
  13.     sort(all, all + cnt);
  14.     for (int i = 0; i < cnt; i++) {
  15.         if (i == 0 || all[i] != all[i - 1])
  16.             dis[dcnt++] = all[i];
  17.     }
  18. }
  20. int query(int x) {
  21.     return lower_bound(dis, dis + dcnt, x) - dis;
  22. }
  24. int main() {
  25.     cin >> n;
  26.     for (int i = 0; i < n; i++) {
  27.         scanf("%d", &a[i]);
  28.         all[cnt++] = a[i];
  29.     }
  31.     cin >> m;
  32.     for (int i = 0; i < m; i++) {
  33.         scanf("%d", &b[i]);
  34.         all[cnt++] = b[i];
  35.     }
  36.     for (int i = 0; i < m; i++) {
  37.         scanf("%d", &c[i]);
  38.         all[cnt++] = c[i];
  39.     }
  41.     discrete();
  43.     for (int i = 0; i < n; i++) {
  44.         int id = query(a[i]);
  45.         sum[id]++;
  46.     }
  48.     int max1 = -1, max2 = -1, idx = -1;
  50.     for (int i = 0; i < m; i++) {
  51.         int id1 = query(b[i]), id2 = query(c[i]);
  52.         if (sum[id1] > max1) {
  53.             max1 = sum[id1];
  54.             max2 = sum[id2];
  55.             idx = i + 1;
  56.         } 
  57.         else if (sum[id1] == max1 && sum[id2] > max2) {
  58.             max2 = sum[id2];
  59.             idx = i + 1;
  60.         }
  61.     }
  63.     cout << idx;
  65.     return 0;
  66. }
  68. // 哈希表
  69. #include <iostream>
  70. #include <algorithm>
  71. #include <unordered_map>
  73. using namespace std;
  75. const int N = 2e5 + 10;
  77. int n, m;
  78. unordered_map<int, int> a;
  80. struct MV {
  81.     int idx, cnt1, cnt2;
  83.     bool operator <(const MV &m) const {
  84.         if (cnt1 == m.cnt1) return cnt2 < m.cnt2;
  85.         return cnt1 < m.cnt1;
  86.     }
  87. } mv[N];
  89. int main() {
  90.     cin >> n;
  91.     for (int i = 1; i <= n; i++) {
  92.         int x;
  93.         scanf("%d", &x);
  94.         a[x]++;    //完成了离散化的工作
  95.     }
  97.     cin >> m;
  98.     for (int i = 1; i <= m; i++) {
  99.         int x;
  100.         scanf("%d", &x);
  101.         mv[i].idx = i;
  102.         mv[i].cnt1 = a[x];
  103.     }
  105.     for (int i = 1; i <= m; i++) {
  106.         int x;
  107.         scanf("%d", &x);
  108.         mv[i].cnt2 = a[x];
  109.     }
  111.     sort(mv + 1, mv + m + 1);
  113.     cout << mv[m].idx;
  115.     return 0;
  116. }

区间和

由于需要遍历数组获取前缀和，而且数组范围过大，因此需要使用离散化
只用哈希表仍然需要遍历，虽然可以再用一个数组记录有数的位置，但是这样做就有些太麻烦了

  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  5. using namespace std;
  7. const int N = 3 * 1e5 + 10;
  9. typedef pair<int, int> PII;
  10. vector<PII> add, query;
  11. // vector<int> alls;
  12. int alls[N], all_size, dsize;
  13. int a[N], s[N];
  15. void discrete() {
  16.     sort(alls, alls + all_size);
  17.     for (int i = 0; i < all_size; i++) {
  18.         if (i == 0 || alls[i] != alls[i - 1])
  19.             alls[dsize++] = alls[i];
  20.     }
  21. }
  23. int find(int x) {
  24.     return lower_bound(alls, alls + dsize, x) - alls + 1;
  25. }
  27. // int find(int x) {
  28. //     int l = 0, r = alls.size() - 1;
  29. //     while (l < r) {
  30. //         int mid = l + (r - l) / 2;
  31. //         if (alls[mid] >= x) r = mid;
  32. //         else l = mid + 1;
  33. //     }
  34. //     return r + 1;
  35. // }
  37. int main() {
  38.     int n, m;
  39.     scanf("%d%d", &n, &m);
  41.     for (int i = 0; i < n; i++) {
  42.         int x, c;
  43.         scanf("%d%d", &x, &c);
  45.         add.push_back({x, c});
  46.         // alls.push_back(x);
  47.         alls[all_size++] = x;
  48.     }
  50.     for (int i = 0; i < m; i++) {
  51.         int l, r;
  52.         scanf("%d%d", &l, &r);
  54.         query.push_back({l, r});
  55.         alls[all_size++] = l;
  56.         alls[all_size++] = r;
  57.         // alls.push_back(l);
  58.         // alls.push_back(r);
  59.     }
  61.     discrete();
  62.     // sort(alls.begin(), alls.end());
  63.     // alls.erase(unique(alls.begin(), alls.end()), alls.end());
  65.     for (auto item: add) {
  66.         int x = find(item.first);
  67.         a[x] += item.second;
  68.     }
  70.     for (int i = 1; i <= dsize; i++) s[i] = s[i - 1] + a[i];
  72.     for (auto item: query) {
  73.         int l = find(item.first), r = find(item.second);
  75.         printf("%d\n", s[r] - s[l - 1]);
  76.     }
  78.     return 0;
  79. }

中位数

知识点

直接看模板题
货仓选址

  1. #include <iostream>
  2. #include <algorithm>
  4. using namespace std;
  6. const int N = 1e5 + 10;
  8. int a[N];
  10. int main() {
  11.     int n;
  12.     cin >> n;
  14.     for (int i = 0; i < n; i++)
  15.         scanf("%d", &a[i]);
  17.     sort(a, a + n);
  19.     int ans = 0;
  21.     for (int i = 0; i < n; i++) ans += abs(a[i] - a[n / 2]);
  23.     cout << ans;
  25.     return 0;
  26. }

可以将其一般化为这样一个问题：给定x[1], …, x[n]，求排序 - 图1的最小值，其中x∈R

  • n为奇数时，取中位数

  • n为偶数时，取x[n/2]~x[n/2+1]中的任何一个数均可

    习题

    第k大数

    知识点

    基于快排的快速选择算法，做法就是在基准值的位置放好之后，如果大于基准值的数的数量cnt>=k，就在左半段寻找第k大数，否则在右半段寻找第k-cnt大数。每次选择了左右之一继续，因此时间复杂度为排序 - 图2

    模板

    ```cpp // 快排模板 void quick_sort(int q[], int l, int r) { if (l >= r) return;

    // 随机选取基准 int idx = l + rand() % (r - l + 1); int x = q[idx]; int i = l - 1, j = r + 1;

    while (i < j) { //x左边的数x

    1.   while (q[++i] < x);
    2.   while (q[--j] > x);
    3.   if (i < j) swap(q[i], q[j]);

    }

    quick_sort(q, l, j); quick_sort(q, j + 1, r); }

// 快速选择 void quick_select(int q[], int l, int r, int k) { if (l >= r) return q[l];

  1. int idx = l + rnad() % (r - l + 1);
  2. int x = q[idx];
  3. int i = l - 1, j = r + 1;
  5. while (i < j) {
  6.     while (q[++i] < x);
  7.     while (q[--j] > x);
  8.     if (i < j) swap(q[i], q[j]);
  9. }
  11. int tmp = j - l + 1;
  12. if (tmp < k) return quick_select(q, j + 1, r, k - tmp);
  13. else return quick_select(q, l, j, k);

}

  1. <a name="WIflP"></a>
  2. # 逆序对
  3. <a name="kBGpS"></a>
  4. ## 知识点
  5. 定义：对于一个序列a，若i<j并且a[i]>a[j]，则称a[i]与a[j]构成逆序对<br />使用归并排序可以在O(nlogn)时间求出逆序对个数<br />左右两半各自内部的逆序对数目作为子问题，只考虑merge即可
  6. <a name="zDOr5"></a>
  7. ## 模板
  8. ```cpp
  9. // 归并排序
  10. void merge_sort(int a[], int l, int r) {
  11.     if (l >= r) return;
  13.     int mid = l + r >> 1;
  14.     merge_sort(a, l, mid);
  15.     merge_sort(a, mid + 1, r);
  17.     int i = l, j = mid + 1, k = 0;
  18.     while (i <= mid && j <= r) {
  19.         if (a[i] <= a[j]) tmp[k++] = a[i++];
  20.         else tmp[k++] = a[j++];
  21.     }
  22.     while (i <= mid) tmp[k++] = a[i++];
  23.     while (j <= r) tmp[k++] = a[j++];
  25.     for (int i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j];
  26. }
  28. // 求逆序对数目
  29. typedef long long LL;
  30. LL merge_sort(int a[], int l, int r) {
  31.     if (l >= r) return;
  33.     int mid = l + r >> 1;
  34.     LL cnt = merge_sort(a, l, mid);
  35.     cnt += merge_sort(a, mid + 1, r);
  37.     int i = l, j = mid + 1, k = 0;
  38.     while (i <= mid && j <= r) {
  39.         if (a[i] <= a[j]) {
  40.             tmp[k++] = a[i++];
  41.             cnt += mid - i + 1;
  42.         }
  43.         else tmp[k++] = a[j++];
  44.     }
  45.     while (i <= mid) tmp[k++] = a[i++];
  46.     while (j <= r) tmp[k++] = a[j++];
  48.     for (int i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j];
  50.     return cnt;
  51. }

STL

大多数情况下，排序直接使用C++自带的sort，通过自定义排序函数cmp来解决各种问题

  • 对字符串排序，默认的排序方法和strcmp一致，逐char比较
    • strcmp：相等时返回0，ab返回正数
    • 需要比较字符串长度的话使用strlen

      习题

      字符串排序2

      非英文字母的其它字符保持原来的位置
      可以将英文字母单独拿出来排序
      最后如果是英文字母，按照单独拿出来的排序结果依次补上，不是英文字母直接用 ```cpp

      include

      include

      include

      include

      include

using namespace std;

const int N = 1005;

struct alpha { char c; int id; }alphas[N];

char s[N];

bool cmp(alpha a, alpha b) { char c1 = a.c, c2 = b.c; if (c1 >= ‘A’ && c1 <= ‘Z’) c1 = c1 - ‘A’ + ‘a’; if (c2 >= ‘A’ && c2 <= ‘Z’) c2 = c2 - ‘A’ + ‘a’;

  1. if (c1 == c2) return a.id < b.id;
  2. return c1 < c2;

}

int main() {

  1. #ifdef SUBMIT
  2. freopen("in.txt", "r", stdin);
  3. freopen("out.txt", "w", stdout);
  4. long _begin_time = clock();
  5. #endif
  7. while (gets(s)) {
  8.     int len = strlen(s);
  9.     int cnt = 0;
  10.     for (int i = 0; i < len; i++) {
  11.         if (isalpha(s[i])) {
  12.             alphas[cnt].c = s[i];
  13.             alphas[cnt].id = cnt;
  14.             cnt++;
  15.         }
  16.     }
  18.     sort(alphas, alphas + cnt, cmp);
  20.     cnt = 0;
  21.     for (int i = 0; i < len; i++) {
  22.         if (isalpha(s[i])) {
  23.             printf("%c", alphas[cnt++]);
  24.         }
  25.         else {
  26.             printf("%c", s[i]);
  27.         }
  28.     }
  29.     puts("");
  30. }
  32. #ifdef SUBMIT
  33. long _end_time = clock();
  34. printf("\n\ntime = %ld ms", _end_time - _begin_time);
  35. #endif
  37. return 0;

} ```

TOPK

  • 全局排序，O(n*lg(n))
  • 局部排序，只排序TopK个数，O(n*k)
    • 选择排序选出最小的K个数
  • 堆，TopK个数也不排序了，O(n*lg(k))
    • 选出的K个数不需要顺序，可以维护一个大小为K的堆
    • 建堆复杂度O(k)，调整复杂度最小O(n)，最大O(nlogk)，总体最小O(n)，最大O(nlogk)

  • 快速选择：选出第K大的数，那么它左侧加上它就是TOPK

    • 加上随机划分，复杂度可以降至O(n)
    • 空间开销大，需要把所有数都读进来

      稳定排序

  • 使用stable_sort，用法和sort完全一致，是稳定的

    • stable_sort 基于归并排序，属于非原地排序，时间复杂度上与sort相差无几，当初做实验非递归的版本甚至要快
  • 为每个元素增加一个属性下标，进行区分，利用cmp比较规则