Skip to content

Commit c5b78fa

Browse files
liuyuboboboliuyubobobo
committed
0315 solved.
1 parent a7732b2 commit c5b78fa

File tree

5 files changed

+283
-0
lines changed

5 files changed

+283
-0
lines changed

‎0315-Count-of-Smaller-Numbers-After-Self/cpp-0315/CMakeLists.txt

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
cmake_minimum_required(VERSION 3.12)
2+
project(cpp_0315)
3+
4+
set(CMAKE_CXX_STANDARD 11)
5+
6+
add_executable(cpp_0315 main3.cpp)

‎0315-Count-of-Smaller-Numbers-After-Self/cpp-0315/main.cpp

Lines changed: 102 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,102 @@
1+
/// Source : https://leetcode.com/problems/count-of-smaller-numbers-after-self/
2+
/// Author : liuyubobobo
3+
/// Time : 2018-12-03
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <set>
8+
9+
using namespace std;
10+
11+
12+
/// Using BST
13+
/// Time Complexity: O(nlogn)
14+
/// Space Complexity: O(n)
15+
class BST{
16+
17+
private:
18+
class TreeNode{
19+
public:
20+
int val, sz;
21+
TreeNode *left, *right;
22+
TreeNode(int val): val(val), sz(1), left(NULL), right(NULL){}
23+
};
24+
TreeNode* root;
25+
26+
public:
27+
BST(): root(NULL){}
28+
29+
void add(int x){
30+
root = add(root, x);
31+
}
32+
33+
int smaller_than(int x){
34+
return smaller_than(root, x);
35+
}
36+
37+
private:
38+
TreeNode* add(TreeNode* node, int x){
39+
if(!node)
40+
return new TreeNode(x);
41+
42+
if(x <= node->val)
43+
node->left = add(node->left, x);
44+
else
45+
node->right = add(node->right, x);
46+
node->sz ++;
47+
return node;
48+
}
49+
50+
int smaller_than(TreeNode* node, int x){
51+
52+
if(!node)
53+
return 0;
54+
55+
if(x <= node->val)
56+
return smaller_than(node->left, x);
57+
return (node->left ? node->left->sz : 0) + 1 + smaller_than(node->right, x);
58+
}
59+
};
60+
61+
class Solution {
62+
public:
63+
vector<int> countSmaller(vector<int>& nums) {
64+
65+
vector<int> res;
66+
if(nums.size() == 0)
67+
return res;
68+
69+
res.push_back(0);
70+
if(nums.size() == 1)
71+
return res;
72+
73+
BST bst;
74+
bst.add(nums.back());
75+
for(int i = nums.size() - 2; i >= 0; i --){
76+
bst.add(nums[i]);
77+
res.push_back(bst.smaller_than(nums[i]));
78+
}
79+
reverse(res.begin(), res.end());
80+
return res;
81+
}
82+
};
83+
84+
85+
void print_vec(const vector<int>& vec){
86+
for(int e: vec)
87+
cout << e << " ";
88+
cout << endl;
89+
}
90+
91+
int main() {
92+
93+
vector<int> nums1 = {5, 2, 6, 1};
94+
print_vec(Solution().countSmaller(nums1));
95+
// 2 1 1 0
96+
97+
vector<int> nums2 = {2, 0, 1};
98+
print_vec(Solution().countSmaller(nums2));
99+
// 2 0 0
100+
101+
return 0;
102+
}

‎0315-Count-of-Smaller-Numbers-After-Self/cpp-0315/main2.cpp

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,83 @@
1+
/// Source : https://leetcode.com/problems/count-of-smaller-numbers-after-self/
2+
/// Author : liuyubobobo
3+
/// Time : 2018-12-03
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <set>
8+
9+
using namespace std;
10+
11+
12+
/// Using Merge Sort
13+
/// Sort (value, index) pair to track every element's index
14+
///
15+
/// Time Complexity: O(nlogn)
16+
/// Space Complexity: O(n)
17+
class Solution {
18+
public:
19+
vector<int> countSmaller(vector<int>& nums) {
20+
21+
int n = nums.size();
22+
23+
vector<pair<int, int>> elements;
24+
for(int i = 0; i < n; i ++)
25+
elements.push_back(make_pair(nums[i], i));
26+
27+
vector<int> res(n, 0);
28+
vector<pair<int, int>> aux(n);
29+
merge_sort(elements, 0, n - 1, aux, res);
30+
return res;
31+
}
32+
33+
private:
34+
void merge_sort(vector<pair<int, int>>& arr, int l, int r,
35+
vector<pair<int, int>>& aux, vector<int>& res){
36+
37+
if(l >= r)
38+
return;
39+
40+
int mid = (l + r) / 2;
41+
merge_sort(arr, l, mid, aux, res);
42+
merge_sort(arr, mid + 1, r, aux, res);
43+
if(arr[mid] > arr[mid + 1])
44+
merge(arr, l, mid, r, aux, res);
45+
}
46+
47+
void merge(vector<pair<int, int>>& arr, int l, int mid, int r,
48+
vector<pair<int, int>>& aux, vector<int>& res){
49+
50+
for(int i = l; i <= r; i ++)
51+
aux[i] = arr[i];
52+
int i = l, j = mid + 1;
53+
for(int k = l; k <= r; k ++)
54+
if(i > mid)
55+
arr[k] = aux[j], j ++;
56+
else if(j > r)
57+
arr[k] = aux[i], res[aux[i].second] += j - mid - 1, i ++;
58+
else if(aux[i] <= aux[j])
59+
arr[k] = aux[i], res[aux[i].second] += j - mid - 1, i ++;
60+
else
61+
arr[k] = aux[j], j ++;
62+
}
63+
};
64+
65+
66+
void print_vec(const vector<int>& vec){
67+
for(int e: vec)
68+
cout << e << " ";
69+
cout << endl;
70+
}
71+
72+
int main() {
73+
74+
vector<int> nums1 = {5, 2, 6, 1};
75+
print_vec(Solution().countSmaller(nums1));
76+
// 2 1 1 0
77+
78+
vector<int> nums2 = {2, 0, 1};
79+
print_vec(Solution().countSmaller(nums2));
80+
// 2 0 0
81+
82+
return 0;
83+
}

‎0315-Count-of-Smaller-Numbers-After-Self/cpp-0315/main3.cpp

Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
/// Source : https://leetcode.com/problems/count-of-smaller-numbers-after-self/
2+
/// Author : liuyubobobo
3+
/// Time : 2018-12-03
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <set>
8+
9+
using namespace std;
10+
11+
12+
/// Using Merge Sort
13+
/// Using indexes arr to track every element's index
14+
///
15+
/// Time Complexity: O(nlogn)
16+
/// Space Complexity: O(n)
17+
class Solution {
18+
public:
19+
vector<int> countSmaller(vector<int>& nums) {
20+
21+
int n = nums.size();
22+
23+
vector<int> indexes(n); // indexes[i] : 在排序过程中，nums第i个元素
24+
// 对应初始nums中indexes[i]的位置
25+
// indexes[2] = 5 表示现在nums中第2个元素，在初始nums中索引为5的位置
26+
for(int i = 0; i < n; i ++)
27+
indexes[i] = i;
28+
29+
vector<int> res(n, 0);
30+
vector<int> aux(n);
31+
merge_sort(nums, 0, n - 1, indexes, aux, res);
32+
return res;
33+
}
34+
35+
private:
36+
void merge_sort(vector<int>& arr, int l, int r,
37+
vector<int>& indexes, vector<int>& aux, vector<int>& res){
38+
39+
if(l >= r)
40+
return;
41+
42+
int mid = (l + r) / 2;
43+
merge_sort(arr, l, mid, indexes, aux, res);
44+
merge_sort(arr, mid + 1, r, indexes, aux, res);
45+
if(arr[mid] > arr[mid + 1])
46+
merge(arr, l, mid, r, indexes, aux, res);
47+
}
48+
49+
void merge(vector<int>& arr, int l, int mid, int r,
50+
vector<int>& indexes, vector<int>& aux, vector<int>& res){
51+
52+
for(int i = l; i <= r; i ++)
53+
aux[i] = arr[i];
54+
55+
vector<int> new_indexes(r - l + 1);
56+
int i = l, j = mid + 1;
57+
for(int k = l; k <= r; k ++)
58+
if(i > mid)
59+
arr[k] = aux[j], new_indexes[k - l] = indexes[j], j ++;
60+
else if(j > r)
61+
arr[k] = aux[i], new_indexes[k - l] = indexes[i], res[indexes[i]] += j - mid - 1, i ++;
62+
else if(aux[i] <= aux[j])
63+
arr[k] = aux[i], new_indexes[k - l] = indexes[i], res[indexes[i]] += j - mid - 1, i ++;
64+
else
65+
arr[k] = aux[j], new_indexes[k - l] = indexes[j], j ++;
66+
67+
for(int k = l; k <= r; k ++)
68+
indexes[k] = new_indexes[k - l];
69+
}
70+
};
71+
72+
73+
void print_vec(const vector<int>& vec){
74+
for(int e: vec)
75+
cout << e << " ";
76+
cout << endl;
77+
}
78+
79+
int main() {
80+
81+
vector<int> nums1 = {5, 2, 6, 1};
82+
print_vec(Solution().countSmaller(nums1));
83+
// 2 1 1 0
84+
85+
vector<int> nums2 = {2, 0, 1};
86+
print_vec(Solution().countSmaller(nums2));
87+
// 2 0 0
88+
89+
return 0;
90+
}

‎readme.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -280,6 +280,8 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
280280
| 308 | [Range Sum Query 2D - Mutable](https://leetcode.com/problems/range-sum-query-2d-mutable/description/) | | [C++](0308-Range-Sum-Query-2D-Mutable/cpp-0308/) | | |
281281
| 309 | [Best Time to Buy and Sell Stock with Cooldown](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/) | | [C++](0309-Best-Time-to-Buy-and-Sell-Stock-with-Cooldown/cpp-0309/) | | |
282282
| | | | | | |
283+
| 315 | [Count of Smaller Numbers After Self](https://leetcode.com/problems/count-of-smaller-numbers-after-self/) | [无] | [C++](0315-Count-of-Smaller-Numbers-After-Self/cpp-0315/) | | |
284+
| | | | | | |
283285
| 319 | [Bulb Switcher](https://leetcode.com/problems/bulb-switcher/description/) | [无] | [C++](0319-Bulb-Switcher/cpp-0319/) | | |
284286
| | | | | | |
285287
| 322 | [Coin Change](https://leetcode.com/problems/coin-change/description/) | [solution](https://leetcode.com/problems/coin-change/solution/) | [C++](0322-Coin-Change/cpp-0322/) | | |

0 commit comments

Comments
 (0)