您的浏览器不支持CSS3,建议使用Firfox、Chrome等浏览器,以取得最佳显示效果

LeetCode:下一个排列

开发技术 151℃ 0 2个月前 (04-04)

摘要

LeetCode:下一个排列

题目

31. 下一个排列

计算字典序排列的下一个排列,原地算法。

例如 1,2,3 的字典序排列如下。

1  2  3
1  3  2
2  1  3
2  3  1
3  1  2
3  2  1

分析

对于 123 做分析发现:

  • 当所有值递减(或相等)时,也就组成了最大值,下一个排列为全部翻转得到的最小值。
  • 当最后两位递增时,下一个排列只需要交换最后两位即可,例如 1 2 3 --> 1 3 2
  • 当最后两位递减(或相等)时,不能交换最后两位,而需要让倒数第三位增大,也就是从后面找一个刚好更大一点的数据填上去,为了原地操作,直接交换位置。例如 1 3 2 --> 2 3 1

上面第三种情况比较复杂,再找个复杂的例子:

5  2  4  3  1
      ———————
      找到末尾最长的递减序列,[4 3 1] 已经是最大的了,想增加数值,只能增加高位

5  2  4  3  1
      ———————
         ↑
        找到了刚好比2大的数字3

5  2  4  3  1
      ———————
   ↑     ↑
   2 改为 3,原地操作,直接交换

5  3  4  2  1
      ———————
      ↑  ↑  ↑
      需要将 [4 2 1] 改为最小值,即 [1 2 4]
      发现 [4 2 1] 刚好是倒序,翻转即可

5  3  1  2  4
      ———————

考虑到数组中可能有重复元素,再找一个例子:

8  2  4  3  3‘ 2’ 2“ 1
   ↑  ————————————————

8  2  4  3  3‘ 2’ 2“ 1
   ↑  ———↑————————————
   如果2和任意一个3交换,

8  3  4  2  3‘ 2‘ 2“ 1
      ————————————————
      后面的数据就乱了,只能重新排序成最小值。

8  2  4  3  3‘ 2’ 2“ 1
   ↑  ——————↑—————————
   如果2和最末尾的3交换,

8  3‘ 4  3  2  2‘ 2“ 1
      ————————————————
      后面的数据刚好还是递减的,直接翻转就能得到最小值。

8  3‘ 1  2“ 2’ 2  3  4
      ————————————————

所以完整的逻辑是:

  1. 如果整个数组都是递减的,说明是最大值,下一个排列应该是最小值,全部翻转即可。
  2. 找到末尾最长的递减序列,其起始index记为k,满足:
    • [k-1] < [k] >= [k+1] >= .. >= [n-1]
  3. 从最末尾开始,找到第一个刚好大于 [k-1] 的数字 [x],因为 [k] > [k-1] ,这个数字肯定是存在的。
  4. 交换 [k-1][x],然后翻转 [k] ~ [n-1]

代码:

class Solution {
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) return;
        int k = findLastDecSeq(nums);
        if (k == 0) {
            reverse(nums, 0, nums.length-1);
            return;
        }
        int x = findLastLagerVal(nums, k, nums[k-1]);
        swap(nums, x, k-1);
        reverse(nums, decIndex, nums.length-1);
    }

    // return k, [k-1] < [k] >= [k+1] >= ... >= [n-1]
    // find longest decreasing sequence in the end
    public int findLastDecSeq(int[] a) {
        for (int i = a.length - 1; i > 0; --i) {
            if (a[i] > a[i-1]) {
                return i;
            }
        }
        return 0;
    }

    // return largest x, [x] > target
    public int findLastLagerVal(int[] a, int start, int target) {
        for (int i = a.length-1; i >= start; --i) {
            if (a[i] > target) return i;
        }
        return start;
    }

    public void swap(int[] a, int x, int y) {
        int t = a[x];
        a[x] = a[y];
        a[y] = t;
    }

    public void reverse(int[] a, int start, int end) {
        while (start < end) {
            int t = a[start];
            a[start] = a[end];
            a[end] = t;
            start++;
            end--;
        }
    }
}

最后,欢迎扫码关注微信公众号。微软 / Shopee / Coupang / BAT等国内外企业内推、行业和技术交流,也可以加我微信 jzj2015(注明来自博客),拉你进技术群。

本文由原创,转载请注明来源:https://www.paincker.com/leetcode-next-permutation
(标注了原文链接的文章除外)

0

暂无评论

评论前:需填写以下信息,或 登录

用户登录

忘记密码?