c++ - 算法问题的交换次数错误

Question

问题

每当乔治要求莉莉出去玩时，她都会忙着做作业。乔治想帮助她更快地完成任务，但是他不知所措!您可以帮助乔治了解莉莉的作业，以便她和他一起出去玩吗？

考虑一个由n不同的整数arr=[a[0],...,a[n-1]]组成的数组。 George可以多次交换数组的任何两个元素。如果|a[i]-a[i-1]| > 0中0 < i < n的总和最小，则数组很漂亮。

给定数组arr，确定并返回为了使数组漂亮而应执行的最小交换次数。

例如，arr = [7,15,12,3]。最小数组是[3, 7, 12, 15]。为了到达那里，乔治进行了以下交换:

Swap      Result
          [7, 15, 12, 3]
3 7       [3, 15, 12, 7]
7 15      [3, 7, 12, 15]

花了2交换才能使数组漂亮。在可能的漂亮阵列选择中，这是最小的。

Input Format

The first line contains a single integer n , the number of elements in arr . The second line contains n  space-separated integers arr[i].

Constraints

0 < n < 100001 0 < arr[i] < 2000000001

Output Format

Return the minimum number of swaps needed to make the array beautiful.

Sample Input

4 2 5 3 1

Sample Output

2

我的努力

我计算交换次数，比较arr元素及其按升序和降序排序的版本。但是由于某种原因，我得到了错误的结果。

代码

int findSwaps(vector<int>& arr, const vector<int>& sortedArr, std::map<int, int> arrIndexMap) {
    int swaps = 0;
    int size = arr.size();

    for (int i = 0; i < size; i++) {
        if (arr[i] != sortedArr[i]) {
            swaps++;

            int j = arrIndexMap[sortedArr[i]];
            arrIndexMap[arr[i]] = j;
            arrIndexMap[arr[j]] = i;

            arr[j] = arr[i];
            arr[i] = sortedArr[i];
        }
    }

    return swaps;
}

int main() {
    int n;
    cin >> n;
    std::vector<int> arr(n);

    for (int i = 0; i < n; i++) {
        int value;
        cin >> value;
        arr.push_back(value);
    }

    std::map<int, int> arrIndexMap;
    for (int i = 0; i < n; i++) {
        arrIndexMap[arr[i]] = i;
    }

    std::vector<int> sortedArr = arr;
    std::sort(sortedArr.begin(), sortedArr.end());

    std::vector<int> descSortedArr = arr;
    std::sort(descSortedArr.begin(), descSortedArr.end(), std::greater<>());

    int swaps1 = findSwaps(arr, sortedArr, arrIndexMap);
    int swaps2 = findSwaps(arr, descSortedArr, arrIndexMap);
    cout << std::min(swaps1, swaps2);

    return 0;
}

输入

5
3 4 2 5 1

预期输出

2

实际输出

5

Answer 1

您的算法实际上是正确的。但是，有2个C++问题会导致意外行为:

1。
您可以在此处使用等于arr的n元素初始化0 vector :

std::vector<int> arr(n);  

然后在循环中添加n其他元素。

但是根据问题陈述，您的n中必须仅包含arr元素。因此，默认情况下创建一个空 vector :

std::vector<int> arr; 

2。
另一个问题是您通过引用传递了arr，这就是为什么第二次将其传递给findSwaps(...)的原因，它已经是您第一次调用时的修改版本:

因此，您应该按值传递它，以免影响初始的arr:

int findSwaps(vector<int> arr, const vector<int>& sortedArr, std::map<int, int> arrIndexMap)

在完成这两项更改之后，我在上尝试了您的代码，在Hackerrank 上通过了所有测试。