女友问我为什么进字节后不理她了，是不是一进字节就没爱情了？

数据结构和算法

发布于 2025-07-10 09:55:54

1030

文章被收录于专栏：数据结构和算法数据结构和算法

刚才我问豆包一个问题，中国加班最厉害的互联网公司有哪些？结果他列出了拼多多，得物，字节，华为，阿里。。。我印象中也确实是这几家加班比较多，甚至有的人入职之后，连和女朋友联系的时间都没有了，还问进入字节，是不是就只有工作没有爱情了？

最近就有一网友，自从入职字节之后，每天早10晚11的，目前状态很差，女友还问他为什么在进入字节之后就不理她了。就这加班程度，估计回去倒头就睡，字节能不能跳都无所谓，只要心脏还能跳就行。

数据结构和算法

《算法秘籍》作者王一博，专注于互联网大厂热点事件和算法题讲解。

791篇原创内容

公众号

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第315题：计算右侧小于当前元素的个数，难度是困难。

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

示例1：

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

示例2：

输入：nums = [-1,-1] 输出：[0,0]

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

问题分析

这题让计算数组中每一个元素右边有多少比它小的元素，看似很简单的一道题，实则不容易，因为数组的长度有可能比较大，如果一个个计算，肯定会超时。

这题我们可以参考归并排序的思路，归并排序的思想是每次把数组分成两部分，一直分下去，直到不能分为止，然后在合并，合并的时候实际上是合并两个有序数组。

既然合并的两个数组是有序的，那么这题就好办了，我们选择从大往小合并，也就是先合并大的，在合并小的，如果前面的元素大于后面的元素，那么前面的元素一定大于后面元素之前的所有元素，有点绕，没关系，我们举个例子，比如我们要合并下面两个有序数组。

[2,4,5,8,9]和[1,3,6,10]

当前面的 8 和后面的 6 比较的时候，因为前面的 8 比后面的 6 大，所以 8 一定大于 6 以及它之前的所有元素，它的个数是 3 ，我们只需要累加即可。

这里在计算之前需要把数组转化一下，因为数组合并的时候位置会发生变化，我们需要先记录下每个元素的值和它对应的下标，代码如下。

JAVA：

public List<Integer> countSmaller(int[] nums) {
    int n = nums.length;
    int[] res = newint[n];// 计算的结果
    int[][] arr = newint[n][];// 记录原数组的值和下标
    for (int i = ; i < n; i++)
        arr[i] = newint[]{nums[i], i};
    mergeSort(arr, , n - , res);// 归并排序
    // 把数组转成list集合
    List<Integer> ans = new ArrayList<>(n);
    for (int num : res)
        ans.add(num);
    return ans;
}

public void mergeSort(int[][] arr, int left, int right, int[] res) {
    if (left < right) {
        int mid = (left + right) >>> ;
        mergeSort(arr, left, mid, res);// 递归左边部分。
        mergeSort(arr, mid + , right, res);// 递归右边部分。
        merge(arr, left, mid, right, res);//  合并
    }
}

// 合并两个有序的数组，从后往前开始合并。
// 前面数组范围[left,center]，后面数组的范围[center+1,right]。
private void merge(int[][] arr, int left, int center, int right, int[] res) {
    int len = right - left + ;// 两个子数组的总长度。
    int[][] tmp = newint[len][];
    int index = len - ;
    int end1 = center;// 前面数组末尾的位置。
    int end2 = right;// 后面数组末尾的位置。
    // 使用双指针合并两个有序数组，从后往前合并。
    while (end1 >= left && end2 > center) {
        if (arr[end1][] <= arr[end2][]) {
            tmp[index--] = arr[end2--];
        } else {// 累加右侧小于当前元素的个数
            res[arr[end1][]] += end2 - center;
            tmp[index--] = arr[end1--];
        }
    }

    // 如果第一个数组前面还有数字就把他添加到临时数组中。
    while (end1 >= left)
        tmp[index--] = arr[end1--];
    // 同理，如果第二个数组后面还有数字就把他添加到临时数组中。
    while (end2 > center)
        tmp[index--] = arr[end2--];
    // 把临时数组中的元素放回原数组。
    index = ;
    while (index < len)
        arr[left + index] = tmp[index++];
}

C++：

public:
    vector<int> countSmaller(vector<int> &nums) {
        int n = nums.size();
        vector<int> res(n, ); // 计算的结果
        vector<pair<int, int>> arr(n); // 记录原数组的值和下标
        for (int i = ; i < n; i++)
            arr[i] = {nums[i], i};
        mergeSort(arr, , n - , res); // 归并排序
        return res;
    }

    void mergeSort(vector<pair<int, int>> &arr, int left, int right, vector<int> &res) {
        if (left < right) {
            int mid = left + (right - left) / ;
            mergeSort(arr, left, mid, res); // 递归左边部分
            mergeSort(arr, mid + , right, res); // 递归右边部分
            merge(arr, left, mid, right, res); // 合并
        }
    }

    // 合并两个有序的数组，从后往前开始合并
    // 前面数组范围[left,center]，后面数组的范围[center+1,right]
    void merge(vector<pair<int, int>> &arr, int left, int center, int right, vector<int> &res) {
        int len = right - left + ; // 两个子数组的总长度
        vector<pair<int, int>> tmp(len);
        int index = len - ;
        int end1 = center; // 前面数组末尾的位置
        int end2 = right; // 后面数组末尾的位置

        // 使用双指针合并两个有序数组，从后往前合并
        while (end1 >= left && end2 > center) {
            if (arr[end1].first <= arr[end2].first) {
                tmp[index--] = arr[end2--];
            } else { // 累加右侧小于当前元素的个数
                res[arr[end1].second] += end2 - center;
                tmp[index--] = arr[end1--];
            }
        }
        // 如果第一个数组前面还有数字就把他添加到临时数组中
        while (end1 >= left)
            tmp[index--] = arr[end1--];
        // 同理，如果第二个数组后面还有数字就把他添加到临时数组中
        while (end2 > center)
            tmp[index--] = arr[end2--];
        // 把临时数组中的元素放回原数组
        for (int i = ; i < len; i++) {
            arr[left + i] = tmp[i];
        }
    }

笔者简介

博哥，真名：王一博，毕业十多年，《算法秘籍》作者，专注于数据结构和算法的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解900多题，对算法题有自己独特的解题思路和解题技巧。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2025-07-08，如有侵权请联系 cloudcommunity@tencent.com 删除

int