前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode: Permutations II

Leetcode: Permutations II

作者头像
卡尔曼和玻尔兹曼谁曼
发布2019-01-22 15:16:53
2980
发布2019-01-22 15:16:53
举报
文章被收录于专栏:给永远比拿愉快

题目: Given a collection of numbers that might contain duplicates, return all possible unique permutations.

代码语言:javascript
复制
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1]. 

这道题和前面Leetcode: Permutations类似,不过给定序列中有重复的序列。 采用Leetcode: Permutations思路二,不过我们在交换的过程中发现有相同元素出现的时候不进行交换就OK了。

C++参考代码: (可以对比Leetcode: Permutations思路二的代码,其实两者改动的地方就是啊判断要不要交换)

代码语言:javascript
复制
class Solution
{
private:
    vector<vector<int>> result;
    int size;
    //这个isSwap函数是比原来的Permutation I中新添加的函数
    //该函数用来判断current位置的元素要不要进行交换
    bool isSwap(vector<int> num, int begin, int current)
    {
        for (int i = begin; i < current; ++i)
        {
            if (num[i] == num[current]) return false;
        }
        return true;
    }
    void permuate(vector<int> &num, int index)
    {
        if (index == size)
        {
            result.push_back(num);
            return;
        }
        for (int i = index; i < size; ++i)
        {
            if (i != index && !isSwap(num, index, i)) continue;//这句是新添加的,用来判断如果给定的序列中有重复元素,则跳过重复元素
            swap(num[index], num[i]);//交换i和index元素
            permuate(num, index + 1);//计算除去index元素,后面元素的全排列
            swap(num[index], num[i]);//再换回来
        }
    }
public:
    vector<vector<int> > permuteUnique(vector<int> &num)
    {
        size = int(num.size());
        permuate(num, 0);
        return result;
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2015年04月19日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档