一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 291|回复: 1
收起左侧

[算法题] Permutation II 这个test case 为啥不过呢

[复制链接] |试试Instant~ |关注本帖
hanrui_542 发表于 2015-10-7 00:40:24 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
Java版的OK, C++版的为啥总是过不了{2, 2, 3, 3, 3}这个case, 返回是{}。代码应该没错,leetcode custom testcase结果是正确的。
lintcode答案Java:http://www.jiuzhang.com/solutions/permutations-ii/

C++版代码:
  1. class Solution {
  2. public:
  3.     /**
  4.      * @param nums: A list of integers.
  5.      * @return: A list of unique permutations.
  6.      */
  7.     vector<vector<int> > permuteUnique(vector<int> &nums) {
  8.         // write your code here
  9.         vector<vector<int> > results;
  10.         vector<int> permutation;
  11.         int n = nums.size();
  12.         if (n == 0)
  13.             return results;
  14.         vector<bool> visited(0);
  15.         
  16.         sort(nums.begin(), nums.end());
  17.         
  18.         helper(nums, n, visited, permutation, results);
  19.         
  20.         return results;
  21.     }
  22.    
  23.     void helper(vector<int> &nums, int n, vector<bool> &visited, vector<int> &permutation,
  24.             vector<vector<int> > &results) {
  25.         
  26.         if (permutation.size() == n) {
  27.             results.push_back(permutation);
  28.             return;
  29.         }
  30.         
  31.         for (int i = 0; i < n; i++) {
  32.             if (visited[i] == 1 || i != 0 && nums[i] == nums[i -1] && visited[i - 1]) {
  33.                 continue;
  34.             }
  35.             visited[i] = 1;
  36.             permutation.push_back(nums[i]);
  37.             helper(nums, n, visited, permutation, results);
  38.             permutation.pop_back();               
  39.             visited[i] = 0;
  40.         }
  41.     }
  42. };
复制代码
plich 发表于 2015-10-7 13:35:38 | 显示全部楼层
本帖最后由 plich 于 2015-10-7 13:40 编辑

if (visited == 1 || i != 0 && nums == nums[i -1] && visited[i - 1])
看起来visited走不满啊……

想了一下,这里应该是漏了一个!: if (visited == 1 || i != 0 && nums == nums[i -1] && !visited[i - 1])

我加了这个,然后改了你的一个声明:vector<bool> visited(n,0); ,就AC了
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 04:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表