题解 | #牛群排列组合#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型二维数组
     */
    public int[][] cow_permutation (int[] nums) {
        ArrayList<List<Integer>> resultList = new ArrayList<>();
        ArrayList<Integer> tempList = new ArrayList<>();
        boolean[] isSelected = new boolean[nums.length];
        backTrack(resultList, tempList, isSelected, nums);
        resultList.sort((o1, o2) -> {
            int index1 = 0, index2 = 0;
            while (index1 < o1.size() && index2 < o2.size()) {
                int cmp  = o1.get(index1++).compareTo(o2.get(index2++));
                if (cmp != 0) {
                    return -cmp;
                }
            }
            return Integer.compare(o1.size(), o2.size());
        });
        int [][] result = new int[resultList.size()][nums.length];
        for (int i = 0; i < resultList.size(); i++) {
            List<Integer> list = resultList.get(i);
            for (int j = 0; j < list.size(); j++) {
                result[i][j] = list.get(j);
            }
        }
        return result;
    }
    private void backTrack(List<List<Integer>> resultList, List<Integer> tempList,
                           boolean [] isSelected, int[] nums) {
        if (tempList.size() == nums.length) {
            resultList.add(new ArrayList<>(tempList));
        }
        for (int i = 0; i < nums.length; i++) {
            // 去重处理
            if ((i != 0) && (nums[i] == nums[i - 1]) && (!isSelected[i-1])) {
                continue;
            }
            if (!isSelected[i]) {
                isSelected[i] = true;
                tempList.add(nums[i]);
                backTrack(resultList, tempList, isSelected, nums);
                isSelected[i] = false;
                tempList.remove(tempList.size() - 1);
            }
        }
    }
}

本题知识点分析：

1.递归

2.回溯

3.数学模拟

4.有序集合存取

5.自定义集合排序

本题解题思路分析：

1.利用递归和回溯排列出所有可能，还需要进行去重判断，因为编号可能重复，造成排列的种类增多。

2.自定义排序，实现Comparator接口,然后比较两个集合每一个元素值大小，返回-cmp,因为是降序，如果值相同，那么就比较集合的长度

3.最后集合转二维数组进行返回即可

本题使用编程语言: Java

如果你觉得本篇文章对你有帮助的话，可以点个赞支持一下，感谢~