2018年4月14日 下午3:54
Count of Smaller Numbers After Self - LeetCode
- 每次遍历的对象是整个序列，而不是原先数组中的某个元素
- 这里使用了分治的方法。我认为这是一种从少到多不断迭代的一个过程，体现了迭代的思想。
- 我在这里和林沐给的答案不同。我的这里参数通过int类型来划分区域，函数是带返回值的。
- 这是同样的思维两种不同的表示方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69class Solution {
public:
std::vector<int> countSmaller(std::vector<int>& nums) {
if(nums.size() == 0){
std::vector<int> temp;
return temp;
}
std::vector<int> count(nums.size());
std::vector<std::pair<int, int>> vec;
//遍历nums建立vec(pair)
for(int i = 0; i < nums.size() ;i++){
std::pair<int, int> temp;
temp.first = nums[i];
temp.second = i;
vec.push_back(temp);
}
merge_sort(0, nums.size()-1, vec, count);
return count;
}
private:
std::vector<std::pair<int, int>> merge_sort_two_vec(std::vector<std::pair<int, int>>& vec1, std::vector<std::pair<int, int>>& vec2, std::vector<int> &count){
std::vector<std::pair<int, int>> vec;
//遍历vec1,vec2
int i = 0;
int j = 0;
while(i < vec1.size() && j < vec2.size()){
if(vec1[i].first <= vec2[j].first){
vec.push_back(vec1[i]);
count[vec1[i].second] += j;//这是计数的规则
i++;
}
else{
vec.push_back(vec2[j++]);
}
}
//省下的补齐
while(i < vec1.size()){
count[vec1[i].second] += j;//这是计数的规则
vec.push_back(vec1[i++]);
}
while(j < vec2.size()){
vec.push_back(vec2[j++]);
}
return vec;
}
//遍历整个序列，而不是原先序列中的某个元素
// 这回一个数组作为处理的单独的对象了，而不是数组中的某一个数。
std::vector<std::pair<int, int>> merge_sort(int left, int right, std::vector<std::pair<int, int>>& vec, std::vector<int> &count){
if(right == left){
std::vector<std::pair<int, int>> vec_temp;
vec_temp.push_back(vec[left]);
return vec_temp;
}
std::vector<std::pair<int, int>> vec1;
std::vector<std::pair<int, int>> vec2;
int mid = (left + right)/2;
vec1 = merge_sort(left, mid, vec, count);
vec2 = merge_sort(mid+1, right, vec, count);
//合并的同时要统计count
return merge_sort_two_vec(vec1, vec2, count);
}
};
- 这是同样的思维两种不同的表示方式