Эта проблема Hackerrank требует пользовательской реализации сортировки слиянием для отслеживания инверсий (свопы, я думаю, это лучший способ обратиться к ней.), Но я не могу захватить правильный счет для некоторых наборов данных.
Заблокирован неудачным тестовым примером в моей текущей реализации с вектором std::vector<int> data { 7, 5, 3, 1 };, выдающим:
Unsorted
- - - - - - - - - -
7 5 3 1
| Left > 7 5
| Right > 3 1
| Left > 7
| Right > 5
| Left > 3
| Right > 1
4 Inversions
Sorted
- - - - - - - - - -
1 3 5 7
Ожидаемый результат - 6 инверсий , но мой алгоритм имеет значение 4 и не совсем уверен, почему мой код не работает для этого набора данных, но работает для других тестовых случаев в Hackerrank.
Моя программа
#include <cstddef>
#include <iostream>
#include <vector>
void merge(std::vector<int> &data, std::vector<int> left, std::vector<int> right, long &inversions)
{
int leftSize = left.size();
int rightSize = right.size();
int leftIndex = 0;
int rightIndex = 0;
std::vector<int> temp;
while (leftIndex < leftSize && rightIndex < rightSize)
{
if (left[leftIndex] <= right[rightIndex]) {
temp.push_back(left[leftIndex++]);
}
else {
temp.push_back(right[rightIndex++]);
inversions++;
}
}
while (leftIndex < leftSize) {
temp.push_back(left[leftIndex++]);
}
while (rightIndex < rightSize) {
temp.push_back(right[rightIndex++]);
}
for(size_t i = 0; i < temp.size(); i++)
{
data[i] = temp[i];
}
}
void mergeSort(std::vector<int> &data, unsigned firstElementIndex, unsigned lastElementIndex, long &inversions, std::string s)
{
if (data.size() <= 1) {
return;
}
std::vector<int> left;
std::vector<int> right;
unsigned pivot = data.size() / 2;
printf("%s| Left > ", s.c_str());
for (unsigned i = firstElementIndex; i < pivot; ++i) {
left.push_back(data[i]);
} for (auto element : left) {
std::cout << element << ' ';
}
printf("\n");
printf("%s| Right > ", s.c_str());
for (unsigned i = pivot; i <= lastElementIndex; ++i) {
right.push_back(data[i]);
} for (auto element : right) {
std::cout << element << ' ';
}
printf("\n");
s.append(" ");
mergeSort(left, firstElementIndex, pivot - 1, inversions, s);
mergeSort(right, pivot - pivot, data.size() - 1 - pivot, inversions, s);
merge(data, left, right, inversions);
}
long countInversions(std::vector<int> &data)
{
long inversions = 0.0;
std::string s = "";
mergeSort(data, 0, data.size() - 1, inversions, s);
return inversions;
}
/*
If I wanted to hack this I could
long countInversions(std::vector<int> &data)
{
long inversions = 0.0;
std::string s = "";
std::vector<int> haxor { 7, 5, 3, 1 };
if (data == haxor)
{
inversions = 6;
}
else
{
mergeSort(data, 0, data.size() - 1, inversions, s);
}
return inversions;
}
*/
int main()
{
std::vector<int> data { 7, 5, 3, 1 };
for (auto i = 0; i < 10; i++) {
// data.push_back( rand() % 100 + 1 );
}
printf("Unsorted\n- - - - - - - - - -\n");
for (auto element : data) {
std::cout << element << ' ';
}
printf("\n\n");
long result = countInversions(data);
printf("\n\n%ld Inversions\n", result);
printf("Sorted\n- - - - - - - - - -\n");
for (auto element : data) {
std::cout << element << ' ';
}
printf("\n");
return 0;
}