-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path51_InversePairs.cpp
More file actions
175 lines (128 loc) · 4.41 KB
/
51_InversePairs.cpp
File metadata and controls
175 lines (128 loc) · 4.41 KB
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
//
// Created by mark on 2019/7/24.
// Copyright © 2019年 mark. All rights reserved.
//
/*
说明:
1. 问题:51. 数组中的逆序对
2. 思路:用排序的思想,逆序就是把大小交换过来;每交换一次,就是一个逆序对正序的过程。
1. 把数组分成两个数组,分别统计出数组内部的逆序对数目;
2. 然后在统计出两个相邻数组之间的逆序对数目;
*/
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <assert.h>
#include <cstdio>
#include <fstream>
#include <map>
#include <set>
using namespace std;
// 这个是参考github中的代码,感觉更加清晰
// https://github.com/gatieme/CodingInterviews/tree/master/036-%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E9%80%86%E5%BA%8F%E5%AF%B9
int MergeElem(vector<int> &elem, int start, int mid, int end, vector<int> &temp);
int InversePairsCore(vector<int> &elem, int start, int end, vector<int> &temp);
int InversePairs(vector<int> elem)
{
if(elem.size() == 0)
return 0;
vector<int> temp(elem.size());
int count = InversePairsCore(elem, 0, elem.size() - 1, temp);
return count;
}
//
int InversePairsCore(vector<int> &elem, int start, int end, vector<int> &temp)
{
int sum = 0;
if(start < end)
{
int mid = (start + end) / 2;
sum += InversePairsCore(elem, start, mid, temp); // 找左半段的逆序对数目
sum += InversePairsCore(elem, mid + 1, end, temp); // 找右半段的逆序对数目
sum += MergeElem(elem, start, mid, end, temp); // 分别找完左右两个半段数组后,各自有序。然后找两段之间的逆序对。
}
return sum;
}
// 数组的归并操作,计算两个数组之间的逆序对
int MergeElem(vector<int> &elem, int start, int mid, int end, vector<int> &temp)
{
// [start, mid]:数组左半段; [mid+1, end]:数组右半段
int i = mid;
int j = end;
int k = 0;
int count = 0;
// i,j分别指向两段数组的尾部,比较,把较小的放到临时数组中去
while(i >= start && j > mid)
{
if(elem[i] > elem[j]) // 前面一个数组大于后面对应位置,后面位置之前全为逆序对
{
temp[k++] = elem[i--]; // 从临时数组最后一个位置排序
count += j - mid;
}
else
temp[k++] = elem[j--];
}
while(i >= start) // 前一半数组还未比较完
temp[k++] = elem[i--];
while(j > mid)
temp[k++] = elem[j--];
for(i = 0; i < k; ++i) // 把排序后的元素放入原数组中
elem[end-i] = temp[i];
return count;
}
// 这个是参考书中的代码
int InversePairsCore_book(int* data, int* temp, int start, int end);
int InversePairs_book(int* data, int length)
{
if(data == nullptr || length < 0)
return 0;
int* temp = new int[length];
for(int i = 0; i < length; i++)
temp[i] = data[i];
int count = InversePairsCore_book(data, temp, 0, length - 1);
delete[] temp;
return count;
}
int InversePairsCore_book(int* data, int* temp, int start, int end)
{
if(start == end)
{
temp[start] = data[start];
return 0;
}
int length = (end - start) / 2;
int left = InversePairsCore_book(temp, data, start, start + length); // 归并左半段
int right = InversePairsCore_book(temp, data, start + length + 1, end); // 归并右半段
int i = start + length; // 前段数组最后一个
int j = end; // 后段数组最后一个
int k = end;
int count = 0;
while(i >= start && j >= start + length + 1)
{
if(data[i] > data[j]) // 前半段大,产生逆序对
{
temp[k--] = data[i--];
count += j - start - length;
}
else
temp[k--] = data[j--];
}
for(;i >= start;i--)
temp[k--] = data[i];
for(;j >= start + length + 1; j--)
temp[k--] = data[j];
return left + right + count;
}
int main()
{
vector<int> elem{7,5,6,4};
int sum1 = InversePairs(elem);
cout << "逆序对个数是:" << sum1 << endl;
int elem2[] = {7,5,6,4};
int sum = InversePairs_book(elem2,4);
cout << "逆序对的个数是:" << sum << endl;
return 0;
}