首页 > 试题广场 >

输出元素组成数组的排列组合形式

[编程题]输出元素组成数组的排列组合形式
  • 热度指数：436 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
一个由有限个不同元素组成的数组的所有组合排列形式。
要求排列的顺序以从小到大的顺序排列，
按首列排序，首列相同，则按照第二列排序，前两列相同，则以第三列排序，以此顺序递推。
示例1

输入

[1,2]

输出

[[1,2],[2,1]]

说明

输出结果：
1，2
2，1
以首列进行排序
示例2

输入

[1,2,3]

输出

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

说明

输出结果：
1，2，3
1，3，2
2，1，3
2，3，1
3，1，2
3，2，1
先排首列，首列相同，以第二列的顺序展示。
算法知识视频讲解
添加回答
木析头像 木析
做的时候一直是7/8，差一个测试样例过不去，反过来看WA掉的样例：array为[]时，返回的要是[]，不能是[[]]。修改了一下就过了： 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector<vector<>>
     */
    void dfs(vector<int>& array, int id, set<vector<int>>& res) {
        if(id==array.size()) {
            res.insert(array);
            return ;
        }
        for(int i=id;i<array.size();++i) {
            int x=array[id];
            array[id]=array[i];
            array[i]=x;
            dfs(array,id+1,res);
            array[i]=array[id];
            array[id]=x;
        }
    }
    vector<vector<int> > exportAllOrders(vector<int>& array) {
        //sort(array.begin(),array.end());
        if(array.size()==0) {
            return vector<vector<int>>{};
        }
        set<vector<int>> s;
        vector<vector<int>> res;
        dfs(array,0,s);
        for(auto iter=s.begin(); iter!=s.end(); ++iter)
            res.push_back(*iter);
        return res;
    }
};


发表于 2021-07-05 11:54:14 回复(0)
咸鱼哥666头像 咸鱼哥666
void fun(vector<int> arr, vector<int> se, int n, vector<vector<int>> &res, int num, vector<int> temp)
{
    if (num == 0)
    {
        res.push_back(temp);
    }
    for (int i = 0; i < n; i++)
    {
        if (se[i] == 1) {
            continue;
        }
        else
        {
            vector<int> t_se = se;
            vector<int> temp1=temp;
            int tem_num = num;
            t_se[i] = 1;
            tem_num--;
            temp1.push_back(arr[i]);
            fun(arr, t_se, n, res, tem_num, temp1);
        }
    }
}
vector<vector<int>> exportAllOrders(vector<int> &array)
{
    // write code here
    sort(array.begin(), array.end());
    int n = array.size();
    vector<vector<int>> res;
    vector<int> se(n, 0);
    vector<int> temp;
    fun(array, se, n, res, n, temp);
    return res;
}
//为什么 8组通过了7组，一组不通过，从leetcode复制过来的也有一种测试用例不通过？？？？
发表于 2021-07-03 22:08:30 回复(1)
南屏机修组扛把子头像 南屏机修组扛把子
解析怎么不排序一下啊
发表于 2022-12-15 16:45:58 回复(0)
tauysi头像 tauysi 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > exportAllOrders(vector<int>& array) {
        // write code here
        vector<vector<int> > res;
        if (array.size() == 0) return res;
        sort(array.begin(), array.end());
        do {
            res.push_back(array);
        } while (next_permutation(array.begin(), array.end()));
        return res;
    }
};
发表于 2021-09-25 21:54:46 回复(0)
Sushine头像 Sushine 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型二维数组
     */
    public int[][] exportAllOrders(int[] array) {
        List<List<Integer>> list = permute(array);
        int[][] arr = new int[list.size()][array.length];
         for (int i = 0; i < list.size(); i++) {
            for (int j = 0; j < array.length; j++) {
                arr[i][j] = list.get(i).get(j);
            }
        }
        return arr;
    }


    public List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        List<List<Integer>> list = new ArrayList<>();
        if (len == 0) return list;
        boolean[] used = new boolean[len];
        List<Integer> path = new ArrayList<>();
        dfs(nums, len, 0, path, used, list);
        return list;
    }

    private void dfs(int[] nums, int len, int depth, List<Integer> path, boolean[] used, List<List<Integer>> res) {
        if (depth == len) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < len; i++) {
            if (!used[i]) {
                path.add(nums[i]);
                used[i] = true;
                dfs(nums, len, depth + 1, path, used, res);
                used[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }
}

发表于 2021-09-21 14:45:25 回复(0)
古笙柯。头像 古笙柯。 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型二维数组
     */
    public int[][] exportAllOrders (int[] array) {
        // write code here
        int n = array.length;
        int l = getLength(n);
        int[][] res = new int[l][n];
        Arrays.sort(array);
        List<Integer> ls = new ArrayList<>();
        List<List<Integer>> list = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        back(array,0,ls,list,set);
        for(int i=0;i<list.size();i++){
            List<Integer> temp = list.get(i);
            for(int j=0;j<temp.size();j++){
                res[i][j] = temp.get(j);
            }
        }
        return res;
    }
    public void back(int[] array, int start, List<Integer> ls, List<List<Integer>> list, Set<Integer> set){
        if(ls.size()==array.length){
            list.add(new ArrayList<>(ls));
            return;
        }
        for(int i=0;i<array.length;i++){
            if(!set.contains(i)){
                set.add(i);
                ls.add(array[i]);
                back(array,start+1,ls,list,set);
                set.remove(i);
                ls.remove(ls.size()-1);
            }else{
                continue;
            }
        }
    }
    public int getLength(int n){
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }else{
            return n*getLength(n-1);
        }
        
    }
}
发表于 2021-08-18 19:23:11 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 伴鱼少儿英语 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 信息技术岗 区块链 测试开发工程师 大数据开发工程师 数据分析师 Java工程师
上传者：小小
难度：
6条回答 3797浏览

热门推荐

通过挑战的用户

相关试题

输出元素组成数组的排列组合形式

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号