C++和 Golang 几乎一样的代码，为什么输出不一致？

Leetcode 第 47 题，有重复数字的排列数，原题地址。

我对照着大佬写的 C++代码，自己写了一份 Golang 代码，运行结果总是不一致。

为了解决这个 bug，我专门下载了 goland 和 clion 两个 IDE，Golang 和 C++两边对照着调试，单步调试了好几个小时，还是找不到问题出在哪里。

我单步调试发现了一点点线索，在进行若干个递归步骤后，go 代码会从某行直接跳到下面的某行，没有执行中间的代码（在源码中通过注释标出）。

下面的两段代码都是直接可运行的代码，特地恳请大佬们帮忙 Debug ！

代码比较简单，不需要理解解题步骤，大佬们肉眼对照找一下区别就好了。

感激不尽!

Golang 代码

package main

/*
 * @lc app=leetcode id=47 lang=golang
 *
 * [47] Permutations II
 */
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)
}

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;
    }
}

Akiyu

2019-06-18 21:10:51 +08:00

哦, 看了一下, 这原因不复杂, 也不是什么神秘的 C++隐式操作, 你应该是没有复制数组

在 C++ 中:
void helper(vector<int> num, int start, int j, vector<vector<int> > &res)
这里的 num 签名没有带 '&', 这会是一次完整的拷贝

而 Go 中:
func helper(res *[][]int, nums []int, start int)
这里的传递应该是一个 slice, 是引用类型的 (我猜的, 反正不会发生数据拷贝, 就相当于拷贝指针一样)
(很多数组(slice)的传递都是引用, 我曾经遇到过坑, 至于解法, 就 leetcode 的解法, copy)

-----------------------------

至于为什么不看嘛...
其实代码写得太长太多, 不是闲得没事做, 没人爱看的...
(老外还挺热心的...)

-----------------------------

我是写 C++ 的, 同时在学 Go, 不介意的话
casyup@outlook.com, 邮箱我你的联系方式, 扩个列