leetcode.315. Count of Smaller Numbers After Self_leetcode315

作者：Cpp五条 | 2024-03-13 03:53:04

踩

leetcode315

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].

Example:

Given nums = [5, 2, 6, 1]

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.

Return the array [2, 1, 1, 0].

具体思路

有很多思路可以参考，不过都是O(nlogn)，最经典的思路就是做merge sort。因为merge sort中，要进行合并，合并的时候就可以有大小关系的体现。例如，merge sort的时候先把nums按中点分为left和right，当left和right都有序之后，如果没有逆序的话，left的所有的数应该要小于right的数，left = {a1,a2,a3}, right = {b1,b2,b3}，i = j = 0. 如果i = j = 1的时候，a2>b2>b1, 对于a2就应该记2次逆序，这里不要用left[i] > right[j]时就记录一次逆序.而是要用left[i] <=right[j]时，这个时候证明，有0-(j-1)这么多的元素，都是left[i] > right[j]，即left[i]的逆序，所以这里为left[i]记上j次逆序即可。例如left = {5,6,7}, right = {1,2,3}, j肯定等于3的时候，再对i = 0的元素5对应的逆序数加上3.对应code看看。然后这些跟left[i]逆序的元素在合并之后就ordered了，对于left[i], 再继续递归看看还是否存在right部分，继续在合并的过程中找逆序，找到逆序之后又合并消除逆序，然后。。。。递归。


class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
         vector<int> res;
    if(nums.empty()) return res;
 
    vector<int> vec, copy;
    for(int i=0; i<nums.size(); i++) {
        vec.push_back(i);
        copy.push_back(i);
    }
 
 
    int smaller[nums.size()];
    for(int i=0; i<nums.size(); i++) {
        smaller[i] = 0;
    }
 
 
    help(nums, vec, copy, 0, vec.size()-1, smaller);
 
 
    for(int i: smaller) {
        res.push_back(i);
    }
 
    return res;
 
    }
    void help(vector<int>& nums, vector<int>& vec, vector<int>& copy, int l, int r, int smaller[]) {
 
    if(l==r) return;
 
    int m = l+(r-l)/2;
    help(nums, vec, copy, l, m, smaller);
    help(nums, vec, copy, m+1, r, smaller);
 
    int i=l, j=m+1, k=l;
    while(i<=m || j<=r) {
        if( j==r+1 || (i<=m &&  nums[vec[i]] <= nums[vec[j]])) {
            copy[k++] = vec[i];
            smaller[vec[i]] += j-m-1;
            i++;
        }
        else copy[k++] = vec[j++];
    }
 
    for(int i=l; i<=r; i++) {
        vec[i] = copy[i];
    }
}
 
};

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/227630