时间戳

首页 > 解决方案 > 在 C 中，为什么用 y 交换 x 比用 x 交换 y 更快？

c - 在 C 中，为什么用 y 交换 x 比用 x 交换 y 更快？

问题描述

在一个问题minimum-swaps-2中，arr 是未排序的数组，arr_count 是数组元素的数量，我们需要返回最小交换次数来对数组进行排序，

我试过了：

int minimumSwaps(int arr_count, int* arr) {
    int swap = 0;
    for(int i  = 0; i < arr_count;){
        if(arr[i] != (i + 1)){
            int temp = arr[i];
            arr[i] = arr[arr[i] - 1];
            arr[arr[i] - 1] = temp;
            swap++;
        } else {
            i++;
        }
    }
    return swap;
}

但它没有用。它显示超时错误。即它需要更多的时间来运行！然后我尝试了下面的代码，它成功了！

        int temp = arr[arr[i] - 1];
        arr[arr[i] - 1] = arr[i];
        arr[i] = temp;
        swap++;

两者之间的唯一区别是将 x 与 y 或 y 与 x 交换。它有什么区别？

标签： carrayssortingswap

解决方案

在arr[i] = arr[arr[i] - 1];值arr[i]被更改并且 arr[arr[i] - 1]不再指向相同的存储之后，arr[arr[i] - 1] = temp;写入错误的存储。

所以你实际上并没有交换两个值。如果您将其表示为指针算术，那可能很明显。

        int temp = *(arr + i);
        *(arr + i) = *(arr + temp - 1);
        *(arr + *(arr + i) - 1) = temp;

最后一行等于 *(arr + *(arr + temp - 1) - 1)第 2 行执行之前存在的值，根据任务的定义，这是错误的。

事实上，它给出了明显的解决方案：

        int temp = *(arr + i);
        *(arr + i) = *(arr + temp - 1);
        *(arr + temp - 1) = temp;

或者

        int temp = arr[i];
        arr[i] = arr[temp - 1];
        arr[temp - 1] = temp;

产生从 5 返回的结果minimumSwaps。

基本上你超时了，因为第一个变体无法达到解决方案。

推荐阅读