大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > 排列算法——字典序法

排列算法——字典序法

关键词:排列算法字典序排列算法——字典序法  阅读(970) 赞(18)

[摘要]本文主要是对排列算法——字典序法的讲解,希望对大家学习排列算法——字典序法有所帮助。

  前言

  LeetCode上确实有不少全排列的题目,这里介绍一种字典序方法

  字典序法

  对给定的字符集中的字符规定一个先后关系,在此基础上按照顺序依次产生每个排列。例如字符集{1,2,3},按照字典序生成的全排列是:123,132,213,231,312,321

  参考示例:

  算法流程如下:

  从右向左,找到第一个破坏从右向左递增顺序的数字,在上图的参考示例中,3是第一个破坏递增序列的,因为1,2,4,5已经是一个递增序列了

  从右向左,找到第一个大于step1的数字,这里是4

  交换这两个数字

  逆序4之后的数字序列

  该方法支持数据重复,且在C++STL中被采用

  题目

  Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

  If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order)。

  The replacement must be in-place, do not allocate extra memory.

  Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

  1,2,3 → 1,3,2

  3,2,1 → 1,2,3

  1,1,5 → 1,5,1

  AC代码

  [java] view plaincopyprint?

  public class Solution {

  public void nextPermutation(int[] num) {

  // special case

  if (num == null || num.length <= 1) {

  return;

  }

  // find the partition number which violate the increase trend

  int partition, swapLoc;

  for (partition = num.length - 1; partition - 1 >= 0; partition--) {

  if (num[partition - 1] < num[partition]) {

  break;

  }

  }

 

  partition -= 1;

  // find the first digit which large than Partition number

  if (partition >= 0) {

  for (swapLoc = num.length - 1; swapLoc > partition; swapLoc--) {

  if (num[swapLoc] > num[partition]) {

  break;

  }

  }

  // swap partition number and change number

  int tmp = num[partition];

  num[partition] = num[swapLoc];

  num[swapLoc] = tmp;

  }

  // reverse all the digit on the right of partition index

  for (int i = partition + 1, j = num.length - 1; i < j; i++, j--) {

  int tmp = num[i];

  num[i] = num[j];

  num[j] = tmp;

  }

  }



相关评论