Table of Contents
Count of Smaller Numbers After Self – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Given an integer array nums, return an integer array counts where counts[i] is the number of smaller elements to the right of nums[i].
Example 1:
Input: nums = [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.
Example 2:
Input: nums = [-1] Output: [0]
Example 3:
Input: nums = [-1,-1] Output: [0,0]
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 104
C++ Count of Smaller Numbers After Self LeetCode Solution
class Solution {
protected:
void merge_countSmaller(vector<int>& indices, int first, int last,
vector<int>& results, vector<int>& nums) {
int count = last - first;
if (count > 1) {
int step = count / 2;
int mid = first + step;
merge_countSmaller(indices, first, mid, results, nums);
merge_countSmaller(indices, mid, last, results, nums);
vector<int> tmp;
tmp.reserve(count);
int idx1 = first;
int idx2 = mid;
int semicount = 0;
while ((idx1 < mid) || (idx2 < last)) {
if ((idx2 == last) || ((idx1 < mid) &&
(nums[indices[idx1]] <= nums[indices[idx2]]))) {
tmp.push_back(indices[idx1]);
results[indices[idx1]] += semicount;
++idx1;
} else {
tmp.push_back(indices[idx2]);
++semicount;
++idx2;
}
}
move(tmp.begin(), tmp.end(), indices.begin()+first);
}
}
public:
vector<int> countSmaller(vector<int>& nums) {
int n = nums.size();
vector<int> results(n, 0);
vector<int> indices(n, 0);
iota(indices.begin(), indices.end(), 0);
merge_countSmaller(indices, 0, n, results, nums);
return results;
}
};
Java Count of Smaller Numbers After Self LeetCode Solution
int[] count;
public List<Integer> countSmaller(int[] nums) {
List<Integer> res = new ArrayList<Integer>();
count = new int[nums.length];
int[] indexes = new int[nums.length];
for(int i = 0; i < nums.length; i++){
indexes[i] = i;
}
mergesort(nums, indexes, 0, nums.length - 1);
for(int i = 0; i < count.length; i++){
res.add(count[i]);
}
return res;
}
private void mergesort(int[] nums, int[] indexes, int start, int end){
if(end <= start){
return;
}
int mid = (start + end) / 2;
mergesort(nums, indexes, start, mid);
mergesort(nums, indexes, mid + 1, end);
merge(nums, indexes, start, end);
}
private void merge(int[] nums, int[] indexes, int start, int end){
int mid = (start + end) / 2;
int left_index = start;
int right_index = mid+1;
int rightcount = 0;
int[] new_indexes = new int[end - start + 1];
int sort_index = 0;
while(left_index <= mid && right_index <= end){
if(nums[indexes[right_index]] < nums[indexes[left_index]]){
new_indexes[sort_index] = indexes[right_index];
rightcount++;
right_index++;
}else{
new_indexes[sort_index] = indexes[left_index];
count[indexes[left_index]] += rightcount;
left_index++;
}
sort_index++;
}
while(left_index <= mid){
new_indexes[sort_index] = indexes[left_index];
count[indexes[left_index]] += rightcount;
left_index++;
sort_index++;
}
while(right_index <= end){
new_indexes[sort_index++] = indexes[right_index++];
}
for(int i = start; i <= end; i++){
indexes[i] = new_indexes[i - start];
}
}
Python 3 Count of Smaller Numbers After Self LeetCode Solution
def countSmaller(self, nums):
def sort(enum):
half = len(enum) / 2
if half:
left, right = sort(enum[:half]), sort(enum[half:])
for i in range(len(enum))[::-1]:
if not right or left and left[-1][1] > right[-1][1]:
smaller[left[-1][0]] += len(right)
enum[i] = left.pop()
else:
enum[i] = right.pop()
return enum
smaller = [0] * len(nums)
sort(list(enumerate(nums)))
return smaller
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
Leave a comment below
