【力扣 Hot100】刷题日记

D8 全排列(非回溯法)

全排列原题链接

在刷leetcode的时候，看到这道题目并没法使用像STL的next_permutation方法，感叹C++便利的同时，又惋惜Java并没有类似的API，那我们只能从原理入手了，仿写此算法。

其实回溯法更应该掌握，因为扩展性高，我们学知识本来就是举一反三的，如果这个算法只适用于这道题，那我们深入学习的必要性就没那么大了。

我们来看实现过程：

1. 找到「下降点」i

• 从右向左扫描数组，找到第一个 arr[i] < arr[i+1] 的位置 i。
• 为什么要找这个？因为字典序的排列从右向左最长的非递增序列是当前排列的尾部，我们想找到可以“升高”的那个位置。

说人话就是，这里非递增序列我们先理解为递减序列（其实还包括前后相等），其实是找递减序列的入口，为什么呢？

因为按照字典序来看，这一部分是不便于排列的，因为难以升高，我们得优先换这部分的前一部分。

如果还是不理解，可以继续往后看，看到后面就会明白这里为什么找下降点。

举例：
arr = [1, 3, 5, 4, 2]
从右往左，观察 arr[i] >= arr[i+1]：

• 4 >= 2 → 是
• 5 >= 4 → 是
• 3 >= 5 → 否，3 < 5
  所以 i = 1（对应数字 3）。
• 如果 i < 0，说明整个数组是非递增序列（即当前排列是最大字典序），没有下一个排列，函数返回 false。

2. 找到交换点 j

• 从右向左找到第一个 arr[j] > arr[i] 的位置。
• 在 arr[i] 后面的序列中找一个比 arr[i] 大的最小数字交换，使排列字典序刚好变大一点。

继续上例：
i=1，arr[i]=3
从右往左找第一个比 3 大的元素：

• 2 <= 3 不符合
• 4 > 3 符合，且是最右边的符合条件元素
  所以 j = 3。

3. 交换 arr[i] 和 arr[j]

交换 3 和 4，变成：

[1, 4, 5, 3, 2]

4. 反转 i+1 位置到数组末尾的部分

将 i+1 到末尾的子数组反转（升序排列），保证新排列是字典序中「紧接着」的下一排列。

这里 i+1=2，子数组是 [5, 3, 2]，反转后是 [2, 3, 5]，数组变成：

[1, 4, 2, 3, 5]

这个就是字典序的下一个排列。

既然这样，那么我们需要实现两个函数swap和reverse

class Solution {
     public List<List<Integer>> permute(int[] nums) {
        Arrays.sort(nums); //这段代码用于判断
        List<List<Integer>> ans = new ArrayList<>();
        do{
            List<Integer> temp = new ArrayList<>();
            for (int num : nums) {
                temp.add(num);
            }
            ans.add(temp);
        }while(nextPermutation(nums));

        return ans;
    }

    private static boolean nextPermutation(int[] arr){
        int i = arr.length - 2;
        while(i >= 0 && arr[i] >= arr[i + 1]) i--; //找到下降点
        if(i < 0) return false;

        int j = arr.length - 1;
        while(arr[j] <= arr[i]) j--; //找出比下降点大的

        swap(arr, i, j);
        reverse(arr, i + 1, arr.length - 1);
        return true;
    }

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

    private static void reverse(int arr[], int l, int r){
         while(l < r) swap(arr, l++, r--);
    }
}

如果这篇文章对你有帮助，请点赞评论收藏，创作不易，你的支持是我坚持的动力。