leetcode 315. Count of Smaller Numbers After Self 右侧比自己小元素的数量+暴力求解

你的名字 2022-06-07 01:07 109阅读 0赞

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

这道题题意很简单，最直接的方法就是暴力求解，但是肯定会超时。

想了好久，没有想到方法，网上看到了一个方法，我思考了许久，觉得一般人想不到这个方法，包括我，所以还是暴力求解吧！

代码如下：

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    class Node 
    {
        Node left, right;
        int val, sum, dup = 1;
        public Node(int v) 
        {
            val = v;
        }
    }
    
    /*
     * https://segmentfault.com/a/1190000008233819
     * 多多考虑吧，我觉得一般想不到
     * */
    public class Solution 
    {
        
        public List<Integer> countSmaller(int[] nums)
        {
            Integer[] ans = new Integer[nums.length];
            Node root = null;
            for (int i = nums.length - 1; i >= 0; i--) 
                root = insert(nums[i], root, ans, i, 0);
            return Arrays.asList(ans);
        }
    
        private Node insert(int num, Node node, Integer[] ans, int i, int preSum) 
        {
            if (node == null) 
            {
                node = new Node(num);
                ans[i] = preSum;
            } else if (node.val == num) 
            {
                node.dup++;
                ans[i] = preSum + node.sum;
            } else if (node.val > num) 
            {
                node.sum++;
                node.left = insert(num, node.left, ans, i, preSum);
            } else 
                node.right = insert(num, node.right, ans, i, preSum + node.dup + node.sum);
            return node;
        }
    
    
        /*
         * 暴力求解，但是会超时
         * */
        public List<Integer> countSmallerByBruceFore(int[] nums) 
        {
            List<Integer> res=new ArrayList<>();
            if(nums==null ||nums.length<=0)
                return res;
            for(int i=0;i<nums.length;i++)
            {
                int count=0;
                for(int j=i+1;j<nums.length;j++)
                {
                    if(nums[j]<nums[i])
                        count++;
                }
                res.add(count);
            }       
            return res;
        }
    }

下面是C++的做法，我想来想去感觉暴力做法最简单明了，

**思路是将给定数组从最后一个开始，用二分法插入到一个新的数组，这样新数组就是有序的，那么此时该数字在新数组中的坐标就是原数组中其右边所有较小数字的个数，**

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    
    class Solution
    {
    public:
        vector<int> countSmaller(vector<int>& a)
        {
            vector<int> res(a.size(), 0);
            vector<int> t;
            for (int i = a.size() - 1; i >= 0; i--)
            {
                int d = distance(t.begin(), lower_bound(t.begin(), t.end(), a[i]));
                res[i] = d;
                t.insert(t.begin() + d, a[i]);
            }
            return res;
        }
    
        vector<int> countSmallerByBruceFource(vector<int>& nums)
        {
            vector<int> res(nums.size(), 0);
            for (int i = 0; i < nums.size(); i++)
            {
                for (int j = i + 1; j < nums.size(); j++)
                {
                    if (nums[j] < nums[i])
                        res[i]++;
                }
            }
            return res;
        }
    };