Leetcode 315.Count of Smaller Numbers After Self 题解

题目链接

Leetcode 315. Count of Smaller Numbers After Self

题目内容

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Input: [5,2,6,1] Output: [2,1,1,0] Explanation: To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element.

解题思路

这周我又选择了一题使用归并算法的题目，题目的要求是要我们计算每个数字右边的比他小的数字的数量。

这里我想到的就是通过把记录逆序数的数量融合在归并排序中，在每一次进行两段有序数组合并的时候，对右边数组中比当前index[s1]小的数字的数目进行记录变量为num，而又因为左边数组有序比nums[indexs[s1]]小的数字必定比nums[indexs[s1+i]]小，所以num在每次合并中只需初始化一次，之后累计下去即可，而当nums[indexs[s1]]push进tmp时，记录当前的num。

通过这样的算法，我们就实现了把记录逆序数数量融合到归并排序之中。其时间复杂度则为T(n) = 2T(n/2) + O(n)，总复杂度就是O(nlogn)

题目代码

class Solution {
public:
    void mergeAnalyse(vector<int>& indexs, int l, int r, vector<int>& results, vector<int>& nums) {
        int count = r - l;
        if (count > 1) {
            int step = count / 2;
            int mid = l + step;
            mergeAnalyse(indexs, l, mid, results, nums);
            mergeAnalyse(indexs, mid, r, results, nums);
            vector<int> tmp;
            tmp.reserve(count);
            int s1 = l;
            int s2 = mid;
            int num = 0;
            while ((s1 < mid) || (s2 < r)) {
                if ( (s2 == r) || ((s1< mid) && (nums[indexs[s1]] <= nums[indexs[s2]]))) {
                    tmp.push_back(indexs[s1]);
                    results[indexs[s1]] += num; // 当前范围右边已经没有比nums[indexs[s1]]的数字，记录结果
                    ++s1;
                } else {
                    tmp.push_back(indexs[s2]);
                    ++num; // 当前范围右边SmallerNumber的数目
                    ++s2;
                }
            } // 归并排序中记录result
            move(tmp.begin(), tmp.end(), indexs.begin()+l);
        }
    }

    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<int> results(n, 0);
        vector<int> indexs(n, 0);
        for (int i = 0; i < n; i++)
            indexs[i] = i;
        mergeAnalyse(indexs, 0, n, results, nums);
        return results;
    }
};

总结

这题和上周的题目十分相像，都是把分析任务融合到我们的归并排序的过程当中去，使得时间复杂度维持在O(NlogN)。通过这两周的两个题目，我体会到了归并排序的魅力，我们可以把它变型成为各种各样高效的算法，实现我们的需求。