Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].
Return the answer in an array.
Example 1:
Input: nums = [8,1,2,2,3] Output: [4,0,1,1,3] Explanation: For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3). For nums[1]=1 does not exist any smaller number than it. For nums[2]=2 there exist one smaller number than it (1). For nums[3]=2 there exist one smaller number than it (1). For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).
Example 2:
Input: nums = [6,5,4,8] Output: [2,1,0,3]
Example 3:
Input: nums = [7,7,7,7] Output: [0,0,0,0]
Constraints:
2 <= nums.length <= 5000 <= nums[i] <= 100
Solution 1: Brute Force
Time complexity: O(n^2)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua class Solution { public: vector<int> smallerNumbersThanCurrent(vector<int>& nums) { const int n = nums.size(); vector<int> ans(n); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (i != j && nums[j] < nums[i]) ++ans[i]; return ans; } }; |
Solution 2: Sort + Binary Search
Time complexity: O(nlogn)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua class Solution { public: vector<int> smallerNumbersThanCurrent(vector<int>& nums) { const int n = nums.size(); vector<int> s(nums); sort(begin(s), end(s)); vector<int> ans(n); for (int i = 0; i < n; ++i) ans[i] = distance(begin(s), lower_bound(begin(s), end(s), nums[i])); return ans; } }; |
Solution 3: Cumulative frequency
Time complexity: O(n)
Space complexity: O(101)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua class Solution { public: vector<int> smallerNumbersThanCurrent(vector<int>& nums) { vector<int> f(101); for (int x : nums) ++f[x]; partial_sum(begin(f), end(f), begin(f)); for (int& x : nums) x = x == 0 ? 0 : f[x - 1]; return nums; } }; |