LeetCode 315. Count of Smaller Numbers After Self

LeetCode 315. Count of Smaller Numbers After Self：题目、思路与代码实现。

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

Example:

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.

题目解析与作答

这个题目很简短，而且很清楚，可以先用最简单的穷举法写出一个解法：

V1 穷举法

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> result;
        for(int i = 0; i < nums.size(); ++i){
            int count = 0;
            for(int e = i+1; e < nums.size(); ++e){
                if(nums[e] < nums[i]) 
                    count++;
            }
            result.push_back(count);
        }
        return result;
    }
};

这个解法竟然可以被Leetcode通过，实在是诧异。但也不妨来分析一下这个穷举法的复杂度：很显然，两层循环

\[O(N^2)\]

---

本文最初发布于简书。

Donate