合并排序中的错误计数：倒置计数

Question

这 Hackerrank problem 要求自定义实现合并排序以跟踪倒置（我认为交换是一种更好的引用方式。），但我无法捕获某些数据集的正确计数。

在我当前的实现中被一个失败的测试用例阻止，使用向量 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;
}

Answer 1

你应该阅读关于 Hackerrank 的讨论：https://www.hackerrank.com/challenges/ctci-merge-sort/forum

问题描述很差 - 论坛中的第 3 次讨论说明了该怎么做。

编辑：以下是关于我提到的讨论的更多信息：

andras_igneczi 2 年前我真的不明白这个例子。为什么我们必须在这个数组的情况下进行 4 次交换：2 1 3 1 2？如果我们交换

合并排序中的错误计数：倒置计数

Wrong Count in Merge Sort: Counting Inversions

c++

mergesort

vector