每日一题[LeetCode 315]计算右侧小于当前元素的个数

简介: 发现leetcode的困难难度做起来还是需要点时间的(还是我太菜了),而且可能大多数人也不能接受,所以明天开始穿插做中等难度题目。

题目描述

给定一个整数数组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. 树状数组

如果你不熟悉这个数据结构的话,你只需要记住它的功能就行。

树状数组是一个数组,有两种操作。一个是对某个位置的元素加值或减值,一个是查询第一个位置到某个位置的元素之和。暴力的话每次查询操作复杂度都是  ,而树状数组可以做到  。

具体细节不介绍了,有现成的模板,会用就行了。

有了这等好东西,就可以把问题这么转化了:新建一个数组bit,其中bit[i]表示i这个数出现的次数。从右边最后一个数开始向左遍历,每遇到一个数nums[i],就把bit[nums[i]]加1,表示这个数多了一个。然后查询bit[0]到bit[nums[i]-1]中的所有次数之和,就表明了当前时刻有多少数比nums[i]小。这一步查询操作正好用到树状数组,最后总的时间复杂度为  。

2. 归并排序

归并排序算法想必大家应该很熟悉了。就是将数组划分为左右两个长度相等的子数组,然后分别递归排序,得到左右两个有序的子数组。然后就是合并了,只要用两个头指针,分别指着两个子数组的开头,然后分别向右移动合并就行了。

那么在这题中怎么用呢?假设左右两个子数组为a[l],...,a[m]和a[m+1],...,a[r],头指针分别为i=l和j=m+1。然后开始合并,首先j向右移动,直到a[j]>=a[i],也就是在右半部分子数组中找到所有小于a[i]的数。然后把这些数依次放入临时数组中,并得到结论:右半部分子数组中比a[i]小的数有j - m - 1个。然后把a[i]也推进临时数组里,重复进行上述过程,直到i>m。最后如果右半部分数组还剩一些数,说明它们是最大的,推入临时数组就行了,最后把临时数组里的数复制进原数组,这部分就排好序了。

要注意的是排序后原来的下标会丢失,所以用一个pair类型保存每一个数和它原来的下标。

3. 二叉搜索树

这种方法也很显然。从最右边一个数开始构建二叉搜索树,结点保存这个数和右边比它小的数的数量。如果新插入一个数,就插入到二叉搜索树中,沿途记得要更新经过的每个结点的数量。如果经过一个结点,并且插入的数比结点的数小,那么就在左子树中继续寻找插入位置,并且结点数量加1。如果插入的数比结点的数大,那么就在右子树中寻找,并且插入的数对应的答案加上该结点的数量。

具体这里就不实现了,主要考察的是数据结构,不想写了。。。

代码

1. 树状数组

class Solution {
public:
    static const int MAXN = 100000;
    int bit[MAXN], x[MAXN], y[MAXN];
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            x[i] = y[i] = nums[i];
        }
        sort(y, y + n);
        int len = unique(y, y + n) - y;
        for (int i = 0; i < n; ++i) {
            x[i] = lower_bound(y, y + len, x[i]) - y + 1;
        }
        memset(bit, 0, sizeof bit);
        vector<int> res;
        for (int i = n-1; i >= 0; --i) {
            res.push_back(sum(x[i]-1));
            add(x[i], 1);
        }
        reverse(res.begin(), res.end());
        return res;
    }
    int lowbit(int x) {
        return x&(-x);
    }
    void add(int i, int x) {
        while (i < MAXN) {
            bit[i] += x;
            i += lowbit(i);
        }
    }
    void sub(int i, int x) {
        while (i < MAXN) {
            bit[i] -= x;
            i += lowbit(i);
        }
    }
    int sum(int i) {
        int s = 0;
        while (i > 0) {
            s += bit[i];
            i -= lowbit(i);
        }
        return s;
    }
};

2. 归并排序

class Solution {
public:
    static const int MAXN = 100000;
    int cnt[MAXN];
    pair<int, int> x[MAXN], y[MAXN];
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            x[i] = make_pair(nums[i], i);
        }
        memset(cnt, 0, sizeof cnt);
        merge_sort(0, n-1);
        vector<int> res(cnt, cnt+n);
        return res;
    }
    void merge_sort(int l, int r) {
        if (l >= r) return;
        int m = (l + r) >> 1;
        merge_sort(l, m);
        merge_sort(m+1, r);
        int idl = l, idr = m + 1, idx = l;
        while (idl <= m) {
            while (idr <= r && x[idr].first < x[idl].first) {
                y[idx++] = x[idr];
                idr++;
            }
            cnt[x[idl].second] += idr - m - 1;
            y[idx++] = x[idl];
            idl++;
        }
        for (int i = l; i < idr; ++i) {
            x[i] = y[i];
        }
    }
};
相关文章
|
2月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
38 1
|
2月前
【LeetCode 27】347.前k个高频元素
【LeetCode 27】347.前k个高频元素
38 0
|
2月前
【LeetCode 06】203.移除链表元素
【LeetCode 06】203.移除链表元素
33 0
|
2月前
【LeetCode-每日一题】移除元素
【LeetCode-每日一题】移除元素
33 0
|
4月前
|
存储 算法
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法,使用双指针技术在原链表上原地删除重复元素,提供了一种时间和空间效率都较高的解决方案。
LeetCode第83题删除排序链表中的重复元素
|
4月前
|
算法 索引
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
这篇文章介绍了LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"的解题方法,通过使用双指针法从数组两端向中间同时查找目标值,有效地找到了目标值的首次和最后一次出现的索引位置。
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
|
4月前
|
算法
LeetCode第27题移除元素
这篇文章介绍了LeetCode第27题"移除元素"的解题方法,通过使用双指针技巧,有效移除数组中特定值的元素并返回新数组的长度。
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
63 6
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
125 2