devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

cakephp update query返回空数组_[力扣315] 索引数组&CDQ分治&归并树

作者：我家小花儿 | 2024-02-15 21:34:43

赞

踩

c++给你一个整数数组 nums,按要求返回一个新数组 counts。数组 counts有该性质 co

fc4ab19c0f1b1a534cc5d60e6d28df5c.png

题目链接

315. 计算右侧小于当前元素的个数

题目描述

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

样例

输入: [5,2,6,1]
输出: [2,1,1,0]
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.

算法1: 离散化＋权值线段树(权值树状数组也可以)

与 493 思路一致，套离散化和线段树的模板即可

思路和模板：[力扣493] 离散化&权值线段树,权值树状数组&CDQ分治

代码(c++)

  1. struct STNode
  2. {
  3.     int start, end;
  4.     int sum;
  5.     STNode *left, *right;
  6.     STNode(int s, int e, int v, STNode* l=nullptr, STNode* r=nullptr)
  7.         :start(s), end(e), sum(v), left(l), right(r) {}
  8.     ~STNode()
  9.     {
  10.         if(left)
  11.         {
  12.             delete left;
  13.             left = nullptr;
  14.         }
  15.         if(right)
  16.         {
  17.             delete right;
  18.             right = nullptr;
  19.         }
  20.     }
  21. };
  22.  
  23. class SegmentTree
  24. {
  25. public:
  26.     SegmentTree()
  27.     {
  28.         root = nullptr;
  29.     }
  30.  
  31.     ~SegmentTree()
  32.     {
  33.         if(root)
  34.         {
  35.             delete root;
  36.             root = nullptr;
  37.         }
  38.     }
  39.  
  40.     void build(int start, int end)
  41.     {
  42.         if(start <= end)
  43.             root = _build(start, end);
  44.     }
  45.  
  46.     void add(int index)
  47.     {
  48.         _add(root, index);
  49.     }
  50.  
  51.     int query(int i, int j)
  52.     {
  53.         if(i > j)
  54.             return 0;
  55.         return _query(root, i, j);
  56.     }
  57.  
  58. private:
  59.     STNode *root;
  60.  
  61.     int _query(STNode* root, int i, int j)
  62.     {
  63.         if(!root) return 0;
  64.         if(root -> start == i && root -> end == j)
  65.             return root -> sum;
  66.         int mid = root -> start + (root -> end - root -> start) / 2;
  67.         if(j <= mid)
  68.             return _query(root -> left, i, j);
  69.         if(mid < i)
  70.             return _query(root -> right, i, j);
  71.         return _query(root -> left, i, mid) + _query(root -> right, mid + 1, j);
  72.     }
  73.  
  74.     void _add(STNode* root, int index)
  75.     {
  76.         if(!root) return;
  77.         if(root -> start == index && root -> end == index)
  78.         {
  79.             ++(root -> sum);
  80.             return;
  81.         }
  82.         int mid = root -> start + (root -> end - root -> start) / 2;
  83.         if(mid >= index)
  84.             _add(root -> left, index);
  85.         else
  86.             _add(root -> right, index);
  87.         ++(root -> sum);
  88.     }
  89.  
  90.     STNode* _build(int start, int end)
  91.     {
  92.         if(start == end)
  93.             return new STNode(start, end, 0);
  94.         int mid = start + (end - start) / 2;
  95.         STNode *left = _build(start, mid);
  96.         STNode *right = _build(mid + 1, end);
  97.         return new STNode(start, end, 0, left, right);
  98.     }
  99. };
  100.  
  101. class Solution {
  102. public:
  103.     vector<int> countSmaller(vector<int>& nums) {
  104.         if(nums.empty()) return vector<int>();
  105.         int n = nums.size();
  106.         vector<int> x(nums.begin(), nums.end()); // 离散化后的值
  107.         sort(x.begin(), x.end());
  108.         x.erase(unique(x.begin(), x.end()), x.end());
  109.         int m = x.size();
  110.  
  111.         SegmentTree segmenttree;
  112.         segmenttree.build(0, m - 1);
  113.         vector<int> result(n);
  114.         result[n - 1] = 0;
  115.         segmenttree.add(_find(nums[n - 1], x));
  116.         for(int i = n - 2; i >= 0; --i)
  117.         {
  118.             result[i] = segmenttree.query(0, _find(nums[i], x) - 1);
  119.             cout << _find(nums[i], x) - 1 << endl;
  120.             segmenttree.add(_find(nums[i], x));
  121.         }
  122.         return result;
  123.     }
  124.  
  125. private:
  126.     int _find(int v, const vector<int>& x)
  127.     {
  128.         return lower_bound(x.begin(), x.end(), v) - x.begin();
  129.     }
  130. };

算法2: CDQ分治 + 索引数组

思路仍然与 493 相同，在归并排序的归并阶段统计信息。但是本题有所不同：归并阶段统计信息时要追溯元素在原始数组中的位置。正常的归并排序过程中，元素的位置已经被打乱，此时要追溯元素在原数组的位置，需要引入索引数组的思想。

考察归并排序过程中的其中一次归并，现在两个子数组 p[left .. mid], q[mid + 1 .. right] 已经有序，现在正在归并。当 p 前进到 i 位置，q 前进到 j 位置时，p[left .. i - 1], q[mid + 1, .. j - 1] 都已经进入了归并排序的辅助数组。此时若 p[i] <= q[j], p[i] 准备进入辅助数组，在进入之前，先要求此时 q 中已近有多少个数字进入了辅助数组，答案是 j - mid。这个是本轮归并对 p[i] 这个数的答案的贡献，因为这些是在 p[i] 的右边且小于 p[i] 的。把历次归并对该数的贡献相加，就得到 p[i] 对应的答案。

29c8859570a41a20e9f4961f7a078ab2.png

索引数组

j - mid 这个贡献要追加到 p[i] 在原数组中的位置上，假设 p[i] 在原数组中的位置是 idx, 则更新贡献值的操作是 result[idx] += j - mid; 但是在归并排序过程中，p[i] 在原数组中的位置已经改变，此时要获取 p[i] 在原数组中的位置 idx，需要一个索引数组。

索引数组的思想：元素在算法的流程中位置变化了，但是后续还需要定位元素在原数组中的位置。此时建立原数组的索引数组，例如 nums = [5, 2, 6, 1], 索引数组为 indexes = [0, 1, 2, 3]，在算法流程中，nums 始终保持不变，改变位置的是 indexes 中的元素，以前是算法完成后需要 nums[i] 有序的性质，现在是要 nums[indexes[i]] 有序的性质。

有类似的思想的结构还有索引堆：堆在插入，更新数据之后，需要做一步向下更新或向上更新，这一步堆数据在数组中的位置就变了。但是有时在堆的不断更新过程中，需要定位到元素在堆数组中的位置，例如 239. 滑动窗口最大值。此时使用索引堆，保存堆数据的数组始终保持不变，不断更新位置的是索引数组。原来在更新算法流程中始终对 nums[i] 保持堆的性质，现在是对 nums[index[i]] 保持堆的性质。

代码(c++)

代码与朴素归并排序基本不变，以前 nums[i] 改变位置的地方，改为 indexes[i] 改变位置，以前给定 i 获取 nums[i] 的地方，改为获取 nums[indexes[i]]

  1. class Solution_2 {
  2. public:
  3.     vector<int> countSmaller(vector<int>& nums) {
  4.         if(nums.empty()) return vector<int>();
  5.         int n = nums.size();
  6.         if(n == 1) return vector<int>({0});
  7.         vector<int> indexes(n, 0);
  8.         for(int i = 1; i < n; ++i)
  9.             indexes[i] = i;
  10.         vector<int> result(n, 0);
  11.         _mergesort(nums, indexes, result, 0, n - 1);
  12.         return result;
  13.     }
  14.  
  15. private:
  16.     void _mergesort(const vector<int>& nums, vector<int>& indexes, vector<int>& result, int left, int right)
  17.     {
  18.         if(left == right) return;
  19.         int mid = left + (right - left) / 2;
  20.         _mergesort(nums, indexes, result, left, mid);
  21.         _mergesort(nums, indexes, result, mid + 1, right);
  22.         _merge(nums, indexes, result, left, mid, right);
  23.     }
  24.  
  25.     void _merge(const vector<int>& nums, vector<int>& indexes, vector<int>& result, int left, int mid, int right)
  26.     {
  27.         vector<int> tmp(right - left + 1, 0);
  28.         int i = left, j = mid + 1, k = 0;
  29.         while(i <= mid && j <= right)
  30.         {
  31.             int pi = nums[indexes[i]], qj = nums[indexes[j]];
  32.             if(pi <= qj)
  33.             {
  34.                 result[indexes[i]] += (j - mid - 1);
  35.                 tmp[k++] = indexes[i++];
  36.             }
  37.             else
  38.                 tmp[k++] = indexes[j++];
  39.         }
  40.         while(i <= mid)
  41.         {
  42.             result[indexes[i]] += (j - mid - 1);
  43.             tmp[k++] = indexes[i++];
  44.         }
  45.         while(j <= right) tmp[k++] = indexes[j++];
  46.         for(i = left, k = 0; i <= right; ++i, ++k)
  47.             indexes[i] = tmp[k];
  48.     }
  49. };

引申: 归并树

1) 归并排序的过程

79025734d3fe7ae9caffaab988e076d1.png
归并排序的过程。divide部分形成了一颗类似线段树的树；combine部分如果左区间[left, mid]对[mid+1, right]的结果有影响，就是CDQ分治的思想

2) CDQ分治

普通分治在合并两个子问题的过程中(图中的combine部分)，[left, mid]内的问题不会对[mid + 1, right]内的问题产生影响，比如排序，线段树的求和、求极值。而CDQ分治合并两个子问题时，还考虑[left, mid]内的修改对[mid + 1, right] 的结果产生的影响，例如求逆序对个数。归并排序CDQ分治的基础。

3) 归并树

归并排序的过程构成了一颗类似线段树的树(图中的divede部分)。那它就可以支持区间查询。

归并树的核心思想，就是利用线段树的建树过程，将归并排序的过程保存。

归并树节点定义：与线段树的唯一区别是线段树节点存的是区间的某指标，例如和，最大值；归并树节点存的是区间内所有的值。

  1. struct MTNode
  2. {
  3.     int start, end;
  4.     vector<int> data;
  5.     MTNode *left, *right;
  6.     MTNode(int s, int e, const vector<int>& nums, MTNode* l=nullptr, MTNode* r=nullptr)
  7.         :start(s),end(e),data(nums),left(l),right(r) {}
  8.     ~MTNode()
  9.     {
  10.         if(left)
  11.         {
  12.             delete left;
  13.             left = nullptr;
  14.         }
  15.         if(right)
  16.         {
  17.             delete right;
  18.             right = nullptr;
  19.         }
  20.     }
  21. };

建树：用给定数组 nums 建归并树：

自底向上地建立节点：叶子节点 start=end, 直接存 nums[start]；如果是非叶子节点，在回溯阶段把左右子节点的数据做归并，作为当前节点存的数据

  1. void build(int start, int end, const vector<int>& nums)
  2. {
  3.     root = _build(start, end, nums);
  4. }
  5.  
  6. MTNode* _build(int start, int end, const vector<int>& nums)
  7. {
  8.     if(start == end)
  9.     {
  10.         return new MTNode(start, end, vector<int>({nums[start]}));
  11.     }
  12.     int mid = start + (end - start) / 2;
  13.     MTNode *left = _build(start, mid, nums);
  14.     MTNode *right = _build(mid + 1, end, nums);
  15.     vector<int> merged((left -> data).size() + (right -> data).size());
  16.     merge((left -> data).begin(), (left -> data).end(), (right -> data).begin(), (right -> data).end(), merged.begin());
  17.     MTNode *cur = new MTNode(start, end, merged, left, right);
  18.     return cur;
  19. }

区间查询

归并树的经典问题：查询的是区间 [a, b] 中值大于 x 的个数

在归并树中找到[a, b]包含的所有不相交的区间对应的节点，分别进行一次二分查找。一次二分查找需要时间O(logN)，而区间[a, b]至多被分为 logN 个不重叠的小区间，这样

可以得到答案。 
  1. int query(int i, int j, int k)
  2. {
  3.     if(i > j) return 0;
  4.     int result = 0;
  5.     _query(root, i, j, k, result);
  6.     return result;
  7. }
  8. void _query(MTNode* root, int i, int j, int k, int& result)
  9. {
  10.     if(root -> start == i && root -> end == j)
  11.     {
  12.         auto pos = upper_bound((root -> data).begin(), (root -> data).end(), k);
  13.         result += (root -> data).end() - pos;
  14.         return;
  15.     }
  16.     int mid = root -> start + (root -> end - root -> start) / 2;
  17.     if(j <= mid)
  18.     {
  19.         _query(root -> left, i, j, k, result);
  20.         return;
  21.     }
  22.     if(i > mid)
  23.     {
  24.         _query(root -> right, i, j, k, result);
  25.         return;
  26.     }
  27.     _query(root -> left, i, mid, k, result);
  28.     _query(root -> right, mid + 1, j, k, result);
  29. }

归并树解决静态数组上多次查询区间 [i, j] 中大于 k 的元素个数的问题的完整代码

  1. #include <vector>
  2. #include <iostream>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. // 区间查询 > x 的数
  8. struct MTNode
  9. {
  10.     int start, end;
  11.     vector<int> data;
  12.     MTNode *left, *right;
  13.     MTNode(int s, int e, const vector<int>& nums, MTNode* l=nullptr, MTNode* r=nullptr)
  14.         :start(s),end(e),data(nums),left(l),right(r) {}
  15.     ~MTNode()
  16.     {
  17.         if(left)
  18.         {
  19.             delete left;
  20.             left = nullptr;
  21.         }
  22.         if(right)
  23.         {
  24.             delete right;
  25.             right = nullptr;
  26.         }
  27.     }
  28. };
  29.  
  30. class MergeTree
  31. {
  32. public:
  33.     MergeTree()
  34.     {
  35.         root = nullptr;
  36.     }
  37.  
  38.     ~MergeTree()
  39.     {
  40.         if(root)
  41.         {
  42.             delete root;
  43.             root = nullptr;
  44.         }
  45.     }
  46.  
  47.     void build(int start, int end, const vector<int>& nums)
  48.     {
  49.         root = _build(start, end, nums);
  50.     }
  51.  
  52.     int query(int i, int j, int k)
  53.     {
  54.         if(i > j) return 0;
  55.         int result = 0;
  56.         _query(root, i, j, k, result);
  57.         return result;
  58.     }
  59.  
  60. private:
  61.     MTNode *root;
  62.  
  63.     void _query(MTNode* root, int i, int j, int k, int& result)
  64.     {
  65.         if(root -> start == i && root -> end == j)
  66.         {
  67.             auto pos = upper_bound((root -> data).begin(), (root -> data).end(), k);
  68.             result += (root -> data).end() - pos;
  69.             return;
  70.         }
  71.         int mid = root -> start + (root -> end - root -> start) / 2;
  72.         if(j <= mid)
  73.         {
  74.             _query(root -> left, i, j, k, result);
  75.             return;
  76.         }
  77.         if(i > mid)
  78.         {
  79.             _query(root -> right, i, j, k, result);
  80.             return;
  81.         }
  82.         _query(root -> left, i, mid, k, result);
  83.         _query(root -> right, mid + 1, j, k, result);
  84.     }
  85.  
  86.     MTNode* _build(int start, int end, const vector<int>& nums)
  87.     {
  88.         if(start == end)
  89.         {
  90.             return new MTNode(start, end, vector<int>({nums[start]}));
  91.         }
  92.         int mid = start + (end - start) / 2;
  93.         MTNode *left = _build(start, mid, nums);
  94.         MTNode *right = _build(mid + 1, end, nums);
  95.         vector<int> merged((left -> data).size() + (right -> data).size());
  96.         merge((left -> data).begin(), (left -> data).end(), (right -> data).begin(), (right -> data).end(), merged.begin());
  97.         MTNode *cur = new MTNode(start, end, merged, left, right);
  98.         return cur;
  99.     }
  100. };
  101.  
  102. int main()
  103. {
  104.     vector<int> nums(20);
  105.     for(int i = 0; i < (int)nums.size(); ++i) nums[i] = i;
  106.     for(int num: nums) cout << num << " ";
  107.     cout << endl;
  108.     random_shuffle(nums.begin(), nums.end());
  109.     for(int num: nums) cout << num << " ";
  110.     cout << endl;
  111.     MergeTree mergetree;
  112.     mergetree.build(0, (int)nums.size() - 1, nums);
  113.     while(true)
  114.     {
  115.         int i, j, k;
  116.         cin >> i >> j >> k;
  117.         cout << mergetree.query(i, j, k) << endl;
  118.     }
  119. }
本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/87201
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号