c++ - 为什么我的 Go 解决方案给出了与 C++ 不同的结果？

Question

两段逻辑完全相同的代码给出了不同的解决方案。

Go 中是否存在错误，还是我在代码中犯了一些愚蠢的错误？

这是一个 leetcode 问题 LeetCode - Permutations II .

下面的 C++ 代码是某人编写的 ACCEPTED 解决方案。

C++ 代码

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int> &num) {
        sort(num.begin(), num.end());
        vector<vector<int>>res;
        helper(num, 0, num.size(), res);
        return res;
    }

    void helper(vector<int> num, int start, int j, vector<vector<int> > &res) {
        if (start == j-1) {
            res.push_back(num);
            return;
        }
        for (int i = start; i < j; i++) {
            if (start == i || num[start] != num[i]) {
                swap(num[start], num[i]);
                helper(num, start + 1, j, res);
            }
        }
    }
};

int main() {
    Solution s;
    vector<int> nums({2,1,2});
    vector<vector<int>> res = s.permuteUnique(nums);
    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[i].size(); j++) {
            cout << " " << res[i][j];
        }
        cout << endl;
    }
}

我把上面的C++代码翻译成了下面的golang代码:

Golang 代码

package main

func permuteUnique(nums []int) [][]int {
    qsort(nums, 0, len(nums)-1)
    res := make([][]int, 0, len(nums))
    helper(&res, nums, 0)
    return res
}

func helper(res *[][]int, nums []int, start int) {
    if start == len(nums)-1 {
        copied := make([]int, len(nums))
        copy(copied, nums)
        *res = append(*res, copied)
        return
    }
    for i := start; i < len(nums); i++ {
        if start == i || nums[start] != nums[i] {               
            nums[i], nums[start] = nums[start], nums[i]
            helper(res, nums, start+1)
        }
    }
}

func main() {
    nums := []int{2,1,2}
    res := permuteUnique(nums)
    for i := 0; i < len(res); i++ {
        for j := 0; j < len(res[0]); j++ {
            print(" ", res[i][j]);
        }
        println()
    }
}

func qsort(nums []int, low, high int) {
    if low >= high {
        return
    }
    i, j, pivot := low, high, nums[low]
    for i < j {
        for i < j && nums[j] >= pivot {
            j--
        }
        nums[i] = nums[j]
        for i < j && nums[i] <= pivot {
            i++
        }
        nums[j] = nums[i]
    }
    nums[i] = pivot
    qsort(nums, low, i-1)
    qsort(nums, i+1, high)
}

输出

以上两段代码都可以立即运行。以下是我的输出:

fondoger@localhost:Desktop$ g++ test.cpp -o app && ./app
 1 2 2
 2 1 2
 2 2 1
fondoger@localhost:Desktop$ go run test.go
 1 2 2
 2 1 2
 2 2 1
 1 2 2

我尝试使用 Goland IDE 和 Clion IDE 调试了几个小时，但我无法找出真相。

Answer 1

试试这个:

func helper(res *[][]int, nums []int, start int) {
    copied := make([]int, len(nums))
    copy(copied, nums)
    nums = copied;
    if start == len(nums)-1 {
        *res = append(*res, nums)
        return
    }
    for i := start; i < len(nums); i++ {
        if start == i || nums[start] != nums[i] {               
            nums[i], nums[start] = nums[start], nums[i]
            helper(res, nums, start+1)
        }
    }
}

当从一种语言移植到另一种语言时，您需要确保您也“移植”了隐含的特性。在 C++ 解决方案中，当调用 helper 函数时，语言将为每次迭代制作 nums 数组的拷贝。你没有克隆这种行为去得到不同的结果。我在 helper 函数的开头添加了 coping num 并且效果很好。