35.Inverse_Pairs_of_Array
2024年2月2日大约 5 分钟约 1571 字
// 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
// 输入一个数组,求出这个数组中的逆序对的总数P
// 并将P对1000000007取模的结果输出。 即输出P%1000000007
// 例如,输入1,2,3,4,5,6,7,0,则会输出:7
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int count = 0;
int InversePairs(vector<int> data) {
mergeSort(data, 0, data.size());
return count % 1000000007;
}
void mergeSort(vector<int>& arr, long lo, long hi) { // 左闭右开[lo, hi)
if (hi - lo < 2) return; // 单元素区间自然有序
long mi = (lo + hi) / 2;
mergeSort(arr, lo, mi); // 排序左区间[lo, mi)
mergeSort(arr, mi, hi); // 排序右区间[mi, hi)
merge(arr, lo, mi, hi); // 归并
}
void merge(vector<int>& arr, long lo, long mi, long hi) {
long frontLen = mi - lo; // 前(左）子向量的长度
auto frontCopy = new int[frontLen];
for (long i = 0; i < frontLen; i++) // 复制前（左）子向量
frontCopy[i] = arr[lo + i];
long i = lo, l = 0, r = mi; // index of total, left, right vector
while (l < frontLen && r < hi) {
if (frontCopy[l] <= arr[r])
arr[i++] = frontCopy[l++];
else {
count += r - mi + 1;
arr[i++] = arr[r++];
}
}
while (l < frontLen) arr[i++] = frontCopy[l++];
while (r < hi) arr[i++] = arr[r++];
delete[] frontCopy;
}
};
int main() {
vector<int> arr{
26819, 20714, 95790, 59566, 59801, 74575, 55921, 11824, 21360, 60903,
32601, 77290, 41967, 16961, 24908, 58967, 77548, 68095, 57695, 52833,
98112, 4569, 64913, 44157, 21769, 28303, 53555, 37085, 11466, 20822,
12, 38285, 57888, 12154, 97851, 17689, 86729, 70124, 45866, 24441,
31027, 78467, 1732, 89347, 11781, 26640, 48314, 89329, 11088, 6009,
58514, 9200, 26931, 23427, 69710, 65052, 68082, 23265, 18489, 79549,
60439, 18501, 17834, 18328, 30656, 32038, 52369, 33737, 2162, 98235,
74531, 49542, 93055, 76263, 38889, 4836, 19255, 3555, 10517, 46695,
9565, 69032, 55896, 52848, 8811, 25606, 17900, 76894, 65223, 36390,
56443, 25662, 71243, 90629, 60342, 18251, 22667, 12712, 68341, 41182,
27299, 42872, 7076, 20354, 35487, 62317, 41542, 71094, 65872, 68412,
17790, 91789, 53796, 90038, 60989, 78959, 15644, 78890, 55853, 97219,
31632, 28648, 39233, 19227, 19278, 99576, 37479, 58297, 28640, 22172,
15831, 72291, 81396, 39259, 92646, 16883, 17928, 50540, 87977, 153,
35304, 22119, 91942, 89100, 12157, 52932, 84412, 44153, 48174, 40265,
41372, 96158, 85266, 96958, 15385, 20896, 12886, 69216, 95545, 41526,
7740, 27729, 30169, 89136, 66988, 39167, 6019, 1269, 89708, 10349,
1422, 41364, 32468, 93364, 46817, 60978, 62648, 31229, 5131, 27174,
71494, 62856, 39684, 73112, 59814, 71422, 94008, 72700, 56990, 5906,
30578, 64731, 33635, 60747, 53867, 16975, 99915, 76239, 18244, 5975,
2940, 19666, 47339, 51760, 29383, 94156, 12738, 92031, 25385, 17870,
35558, 13232, 80726, 75242, 2696, 56892, 63016, 96705, 29592, 20007,
2611, 76522, 1090, 52598, 53621, 54957, 69573, 53536, 47548, 87818,
75863, 66840, 7484, 39555, 18601, 36867, 33711, 31339, 45251, 75449,
65561, 97161, 5033, 46287, 88755, 7729, 3179, 51772, 20786, 49123,
88131, 39749, 41997, 89221, 92347, 95619, 44178, 78273, 65507, 8079,
66091, 41371, 74919, 89927, 80926, 9872, 43147, 30989, 41212, 88398,
22790, 6773, 1911, 44175, 69413, 90666, 68257, 88944, 42438, 89043,
54420, 30569, 45145, 96417, 19790, 53844, 92036, 80321, 32117, 73896,
4752, 98208, 15267, 96023, 4488, 12545, 5896, 47635, 59886, 47108,
52385, 82677, 70233, 54296, 43204, 55998, 44962, 11461, 44943, 3753,
16857, 15715, 50674, 62002, 12132, 86817, 15846, 20521, 83490, 64316,
94417, 88242, 78876, 26036, 617, 83364, 54933, 6513, 30999, 14819,
69973, 99736, 13848, 56559, 54032, 57053, 12557, 15347, 68514, 73852,
19100, 85371, 5919, 86126, 63725, 18052, 72943, 95924, 54925, 72785,
60240, 65694, 77379, 39116, 91730, 77997, 38833, 46663, 862, 69832,
61482, 70836, 69569, 91683, 43747, 39953, 48736, 56304, 55300, 33602,
46509, 90752, 18974, 52428, 76879, 99051, 86832, 66174, 11327, 41757,
55312, 71567, 7451, 32691, 27036, 15533, 27040, 65869, 78548, 27903,
52053, 40031, 98739, 37974, 31714, 58838, 77928, 96802, 15142, 49580,
30404, 78003, 40333, 65730, 46784, 33564, 64782, 33616, 16090, 92461,
91726, 71402, 64029, 15529, 4094, 7417, 31063, 31134, 89638, 9611,
75389, 41691, 65994, 90480, 79666, 14060, 49318, 73946, 27214, 64461,
23526, 57619, 58816, 63859, 23349, 5600, 13775, 4483, 55569, 29866,
13297, 47295, 1268, 93678, 62824, 21714, 1095, 10239, 69201, 90733,
36203, 44590, 48776, 18549, 35071, 44794, 48962, 84389, 18740, 76176,
65202, 58619, 50147, 40371, 38830, 89849, 45971, 52606, 10684, 17892,
82472, 23981, 65187, 92, 17659, 44364, 38159, 18754, 70955, 23712,
25839, 7158, 84654, 90968, 42060, 36077, 35762, 91022, 36819, 70855,
67198, 18373, 29474, 17346, 58744, 68304, 23547, 21068, 37262, 34231,
38960, 36086, 58213, 20500, 52531, 75872, 64864, 90690, 10979, 35819,
30754, 53170, 59330, 15408, 44138, 1390, 51486, 96253, 92412, 88305,
83460, 75962, 23030, 12934, 9660, 81775, 97590, 33207, 19195, 34853,
67439, 58155, 87291, 42004, 95007, 39822, 17876, 59871, 30512, 45207,
12043, 77618, 98378, 87725, 93027, 58868, 89115, 60865, 55121, 97879,
65522, 73841, 88552, 67867, 99854, 70327, 81810, 49413, 89522, 33015,
33204, 64030, 20306, 75208, 59037, 60129, 93085, 35261, 6993, 54644,
63656, 84612, 53022, 51381, 93991, 28243, 40496, 54856, 99716, 54727,
20378, 54650, 44920, 8930, 38869, 44774, 95610, 37031, 10540, 1484,
70046, 43744, 81866, 6705, 18953, 40904, 83186, 28390, 92517, 90179,
83034, 72525, 91143, 52409, 23906, 85134, 97004, 80754, 56342, 96720,
35481, 76720, 51370, 80401, 2003, 6592, 41528, 97613, 43623, 52068,
99097, 30022, 12164, 80964, 53079, 31117, 38220, 36265, 59507, 47089,
42796, 58894, 19614, 33940, 27655, 59872, 35426, 24659, 40626, 91769,
21379, 92459, 84841, 89102, 89212, 86844, 95694, 47092, 809, 55669,
15512, 99907, 85691, 27677, 97223, 38770, 58794, 51795, 91387, 34654,
15236, 34184, 9900, 34850, 84476, 37555, 94722, 36254, 62214, 51700,
28023, 99945, 60511, 29217, 89047, 49723, 16061, 1093, 13168, 16871,
73115, 28680, 33130, 58806, 56357, 46705, 13929, 31504, 14852, 21668,
82510, 30088, 55852, 92410, 81290, 56680, 46317, 92364, 92935, 24883,
44064, 37310, 24828, 4575, 66527, 30228, 70650, 98941, 47673, 83818,
32164, 20788, 28851, 65294, 95947, 85208, 28351, 26228, 33064, 43203,
47896, 15574, 73291, 3749, 24336, 54581, 60429, 87005, 46945, 53364,
11888, 7361, 7027, 53069, 28288, 73554, 99649, 15290, 72495, 47322,
15461, 4659, 68111, 44312, 86305, 80410, 29520, 14656, 6638, 78937,
74211, 70886, 10863, 63854, 90987, 35200, 34787, 51417, 38557, 98084,
21133, 50446, 5445, 28160, 19867, 50085, 18067, 19516, 81728, 90562,
66838, 97189, 95222, 51301, 41501, 31711, 71021, 12536, 54701, 49958,
3099, 25588, 60822, 66954, 16575, 12374, 1741, 84344, 50931, 16178,
21830, 17729, 37975, 66342, 37596, 88061, 84409, 57112, 69789, 91324,
40303, 66978, 2898, 91604, 8479, 777, 39668, 95852, 29665, 10721,
62163, 32765, 52661, 39337, 16071, 85589, 68063, 17812, 69933, 35346,
50342, 8115, 69428, 88318, 90810, 7024, 76379, 75219, 80489, 62520,
82895, 20792, 45850, 85793, 28748, 70681, 86571, 84768, 82885, 16236,
95490, 61400, 65353, 64503, 737, 81424, 50092, 85152, 15589, 36378,
20499, 65931, 60845, 54249, 51655, 13303, 46980, 43227, 10144, 25852,
26122, 47288, 88054, 11916, 92389, 58735, 14839, 77157, 41621, 47427,
88999, 3021, 12781, 53503, 20111, 94205, 3595, 21615, 26146, 56325,
42114, 92078, 17171, 48393, 62679, 68826, 78049, 26012, 12053, 88193,
51864, 38176, 51834, 39919, 66444, 44223, 15006, 81283, 21380, 72979,
28710, 26732, 76001, 57843, 80235, 12464, 52049, 182, 34079, 94547,
56508, 92546, 86625, 73679, 57291, 65657, 58857, 35340, 91669, 70911,
39886, 43533, 25439, 8072, 99804, 8235, 52295, 14811, 89518, 90027,
87790, 34580, 16759, 80143, 92424, 96994, 8959, 60825, 97177, 43039,
55372, 70037, 51937, 58350, 60068, 9228, 24007, 18925, 60921, 15676,
6188, 17159, 75561, 47979, 25231, 75366, 56214, 77526, 6529, 62084,
67553, 94319, 96665, 84313, 90815, 89089, 97659, 99774, 66266, 11188,
42813, 21638, 81225, 11102, 96340, 41293, 36683, 20347, 76571, 97604,
52375, 82759, 31115, 44289, 30739, 56346, 19655, 3305, 50224, 42536,
65390, 34129, 36855, 62055, 34794, 27670, 67496, 32454, 27445, 50114,
43642, 86610, 71752, 41220, 14065, 84445, 82513, 50748, 4792, 75436,
64704, 73520, 58196, 95819, 17809, 5287, 68517, 53816, 8592, 18741,
96352, 90334, 69222, 49559, 68741, 4017, 77230, 36237, 36471, 21027,
2703, 96465, 23989, 74456, 37685, 38054, 75253, 36551, 5154, 80045,
11987, 69858, 69917, 86535, 82029, 87726, 8174, 50546, 33119, 85639,
37894, 23453, 54862, 87454, 92195, 58879, 81036, 44784, 11702, 18415,
47488, 24519, 58756, 38296, 78557, 13163, 13549, 15108, 18317, 9946,
43447, 4528, 79864, 29983, 86557, 67590, 54509, 37104, 25485, 87628,
22743, 63379, 11082, 93957, 67185, 19629, 52836, 64573, 80765, 80890,
82988, 28253, 21762, 58097, 82901, 319, 71260, 96450, 15427, 89577,
22749, 58874, 10457, 2613, 5209, 97015, 86555, 59719, 34119, 12040,
63699, 73214, 91772, 91133, 67172, 58957, 10762, 36360, 23531, 91528,
33603, 22871, 36133, 55365, 80968, 19035, 55684, 52228, 31837, 87463,
58158, 54586, 62689, 84967, 57199, 67899, 81982, 60107, 43970, 32453,
72147, 7669, 5668, 63919, 98803, 89192, 39229, 25917, 41904, 62760,
33797, 75507, 1983, 69931, 30872, 99304, 88966, 2908, 67884, 20803,
90371, 42394, 91742, 27362, 48941, 53664, 9344, 9048, 97634, 41798,
97548, 21655, 63818, 61467, 36810, 69362, 696, 79080, 11266, 79808,
12877, 86774, 98144, 82808, 33998, 97448, 88126, 53259, 65332, 25282,
43630, 7727, 17024, 13043, 35089, 82317, 66707, 60785, 7718, 80693,
18935, 5266, 18701, 82753, 83085, 71863, 52115, 134, 50943, 63382,
79942, 80173, 66508, 94438, 62981},
arr2(arr.begin(), arr.end());
sort(arr.begin(), arr.end());
for (auto i : arr) cout << i << ends;
cout << endl;
Solution s;
s.mergeSort(arr2, 0, arr.size());
for (auto i : arr) cout << i << ends;
cout << endl << "Count is: " << s.count << endl;
bool equal = true;
for (int i = 0; i < arr.size(); ++i)
if (arr[i] != arr2[i]) equal = false;
cout << boolalpha << equal;
}