列印陣列的全部排列

作者：Grey

原文地址：

博客園：列印陣列的全部排列

CSDN：列印陣列的全部排列

無重復值情況

題目描述見: LeetCode 46. Permutations

主要思路

由于是所有排列，所以每個 i 后面位置的元素都有機會來到 i 位置，

定義遞回函式

void p(int[] arr, int i, List<List<Integer>> result)

遞回含義是：陣列 arr 的 i 位置以后的元素，都來到 i 位置（即：和 i 位置的元素交換），得到的排列是多少，

所以，base case 是，當 i 來到 arr 的最后一個元素的位置的時候，此時可以收集一種排列狀況（因為最后一個元素后面沒有元素可以與之交換了）

        if (i == arr.length - 1) {
            // 來到最后一個位置，收集答案
            result.add(Arrays.stream(arr).boxed().collect(Collectors.toList()));
            return;
        }

到普遍位置的時候，即遍歷 i 后面的每個位置，讓每個位置都和 i 位置的值交換

        for (int j = i; j < arr.length; j++) {
            swap(arr, i, j);
            p(arr, i + 1, result);
            swap(arr, i, j);
        }

完整代碼見

class Solution {
    public static List<List<Integer>> permute(int[] arr) {
        if (arr == null ) {
            return Collections.emptyList();
        }
        if (arr.length == 0) {
            List<List<Integer>> ans = new ArrayList<>();
            ans.add(new ArrayList<>());
            return ans;
        }
        List<List<Integer>> result = new LinkedList<>();
        p(arr, 0, result);
        return result;
    }

    private static void p(int[] arr, int i, List<List<Integer>> result) {
        if (i == arr.length - 1) {
            // 來到最后一個位置，收集答案
            result.add(Arrays.stream(arr).boxed().collect(Collectors.toList()));
            return;
        }
        for (int j = i; j < arr.length; j++) {
            swap(arr, i, j);
            p(arr, i + 1, result);
            swap(arr, i, j);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        if (i != j) {
            arr[i] = arr[i] ^ arr[j];
            arr[j] = arr[i] ^ arr[j];
            arr[i] = arr[i] ^ arr[j];
        }
    }
}

有重復值情況

題目描述見: LeetCode 47. Permutations II

有重復值的情況可以借鑒上述遞回方法的思想，我們還是定義如下遞回函式

void p(int i, int[] arr, List<List<Integer>> result)

遞回含義還是：陣列 arr 的 i 位置以后的元素，都來到 i 位置（即：和 i 位置的元素交換），得到的排列是多少，

但是由于有重復值，所以我們在交換之前，需要判斷和 i 交換的元素曾經有沒有訪問過，如下示意圖

當我們將i位置的 a 和 i + n位置的 x 交換過以后，得到了一個全排列的數量，當我們來到i+n+1位置的時候，如果這個位置還是 x ，就無須再和 i 位置的 a 交換了，

為了標識哪個值是否交換過，我們可以定義一個boolean型別的陣列，由于題目中的資料范圍比較小-10<=num[i]<=10, 所以我們只需要一個boolean[] visited = new boolean[21]長度的陣列即可，要判斷某個位置的值 m 是否訪問過，只需要判斷visited[m+10]是否為 TRUE，

完整代碼見

class Solution {
    public static List<List<Integer>> permuteUnique(int[] arr) {
        List<List<Integer>> ans = new ArrayList<>();
        p(0, arr, ans);
        return ans;
    }

    private static void p(int i, int[] arr, List<List<Integer>> result) {
        if (i == arr.length - 1) {
            // 來到最后一個位置，收集答案
            result.add(Arrays.stream(arr).boxed().collect(Collectors.toList()));
            return;
        }
        boolean[] visited = new boolean[21];
        for (int index = i; index < arr.length; index++) {
            if (!visited[arr[index] + 10]) {
                visited[arr[index] + 10] = true;
                swap(index, i, arr);
                p(i + 1, arr, result);
                swap(index, i, arr);
            }
        }
    }

    private static void swap(int i, int j, int[] arr) {
        if (j == i) {
            return;
        }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}

更多

演算法和資料結構筆記

本文來自博客園，作者：Grey Zeng，轉載請注明原文鏈接：https://www.cnblogs.com/greyzeng/p/16749313.html

標籤：其他

上一篇：黑蘋果外接顯示幕廉價方案

下一篇：網路層：資料平面