锐客网

  1. 首页 > 睿知 > >

数据结构与算法分析 面试必考的算法与数据结构详解( 三 )

生活知识经验知识


315. 计算右侧小于目前元素的个数
题目描述
给定一个整数数组 nums 。按要求返回一个新数组 counts 。数组 counts 有该性质：counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量 。
示例
输入：nums = [5,2,6,1]输出：[2,1,1,0] 解释：5 的右侧有 2 个更小的元素 (2 和 1)2 的右侧仅有 1 个更小的元素 (1)6 的右侧有 1 个更小的元素 (1)1 的右侧有 0 个更小的元素提醒
0 <= nums.length <= 100000-10000 <= nums[i] <= 10000
解题思路该题与树状数组经典题「逆序对个数」差不多一样 。假设 (i, j) 为逆序对 。则满足：
i < jnums[i] > nums[j]回到本题 。题目要求 nums[i] 右侧小于它的元素个数 。因此咱们从右往左遍历 nums 数组 。并且定义一个新数组 a 。若遍历到 nums[i] 。则令 a[nums[i]] = 1 。
因此 counts[i] 即为数组 a 中 [-10000, nums[i] - 1] 的区间和 。由于数组的下标为非负数 。因此咱们将 nums[i] 中所有数都加上 10001 。将其原来的范围 [-10000, 10000] 移动到 [1, 20001] 。
再用树状数组维护数组 a 。即可完成此题 。具体细节见下述代码 。
代码实现
class Solution {public:int n;vector<int> c;int lowbit(int x) {return x & (-x);}void update(int x, int v) {for (int i = x; i <= n; i += lowbit(i)) c[i] += v;}int query(int x) {int res = 0;for (int i = x; i; i -= lowbit(i)) res += c[i];return res;}vector<int> countSmaller(vector<int>& nums) {for (int i = 0; i < nums.size(); i++) nums[i] += 10001;n = 2e4 + 1;c.resize(n + 1, 0);for (int i = nums.size() - 1; i >= 0; i--) {int v = nums[i];nums[i] = query(v - 1);update(v, 1);}return nums;}};
493. 翻转对
题目描述给定一个数组 nums。如果 i < j 且 nums[i] > 2 * nums[j] 咱们就将 (i, j) 称作一个重要翻转对 。
你需要返回给定数组中的重要翻转对的数量 。
示例 1
输入: [1,3,2,3,1]输出: 2示例 2
输入: [2,4,3,5,1]输出: 3注意
给定数组的长度不会超过50000 。输入数组中的所有数字都在32位整数的表示范围内 。
解题思路该题与上题思路基本一致 。上题要求的是：
i < jnums[i] > nums[j]但本题要求的是：
i < jnums[i] > 2*nums[j]因此咱们依然可以从右往左遍历 nums 数组 。并且定义一个新数组 a 。若遍历到 nums[i] 。则令 a[2 * nums[i]] = 1 。即 update(2 * nums[i], 1) 。
对于 i 。求所有满足要求的 j 。即为 query(nums[i] - 1) 。
但本题还有一个关键点 。即 nums[i] 的值可能很大 。咱们开不下这么大的空间 。
每当接触这种情况时 。咱们就需要选用「离散化」的手段 。「离散化」的原理是将所有可能出现的数 。如 2 * nums[i] 或 nums[i] 都存入数组 。先排序再去除重复 。然后再依次编号 。
例如 nums[i] 原数组为 [1, 1, 1000000, 2] 。则所有可能出现的数为 [1, 2, 1, 2, 1000000, 2000000, 2, 4] 。将其排序 。得到 [1, 1, 2, 2, 2, 4, 1000000, 2000000] 。再去重得到 [1, 2, 4, 1000000, 2000000] 。
因此咱们可以将所有的 1 映射为 1 。2 映射为 2 。4 映射为 3 。1000000 映射为 4 。2000000 映射为 5 。
由此树状数组的大小则不再取决于 nums[i] 的大小 。而取决于 nums 数组的长度 。
使用「离散化」的技术 。咱们即可完成此题 。具体细节见下述代码 。
代码实现class Solution {public:int n;vector<int> c;int lowbit(int x) {return x & (-x);}void update(int x, int v) {for (int i = x; i <= n; i += lowbit(i)) c[i] += v;}int query(int x) {int res = 0;for (int i = x; i; i -= lowbit(i)) res += c[i];return res;}int reversePairs(vector<int>& nums) {// 离散化set<long long> st;unordered_map<long long, int> mp;for (int i = 0; i < nums.size(); i++) {st.insert(nums[i]);st.insert(2ll * nums[i]);}int idx = 0;for (auto x:st) mp[x] = ++idx;n = idx;c.resize(n + 1, 0);// 求解int ans = 0;for (int i = nums.size() - 1; i >= 0; i--) {ans += query(mp[nums[i]] - 1);update(mp[2ll * nums[i]], 1);}return ans;}};

数据结构与算法分析 面试必考的算法与数据结构详解

文章插图
总结本文主要教学了「树状数组」算法 。该算法的核心功能为 。能在 O(log(n)) 的期间复杂度内「求数组区间和」或者「更新数组中某一点的值」 。
简单来探讨 。如果接触同时支持「求区间和」以及「单点操作」的数据结构题 。则可以往「树状数组」的方向思考 。
【数据结构与算法分析 面试必考的算法与数据结构详解】除此之外 。该算法通过二进制的拆分 。用 O(log(n)) 的效率代替了 O(n) 的简单做法 。其算法思想也值得咱们花期间好好理解 。

推荐阅读


上一篇：遇到一个无赖老公该怎么办？想离,离不了想过更过不好我该咋办？

下一篇：现在搞养殖养什么比较好呢？有亲人养羊,养猪,自己不知道养什么比较好？