hymn

忽有故人心头过,回首山河已是秋。

  menu
132 文章
0 浏览
0 当前访客
ღゝ◡╹)ノ❤️

寻找全排列的下一个数

给出一个正整数,找出这个正整数所有数字全排列的下一个数。

通俗的讲,就是在一个正整数所包含数字的全部组合中,找到一个大于且仅大于原数的新整数。

比如:

输入 12345
输出 12354

输入 12354
输出 12435

image.png

package tree;

import java.util.Arrays;

/**
 * @author: daixyhymn
 * @description: 全排列
 * @date: 2020/11/9 14:06
 */
public class FindNearestNumber {

  public static int[] findNearestNumber(int[] numbers){
    // 1、从后向前查看逆序区域
    int index = findTransferPoint(numbers);
    // 如果返货 0 ,说明数组已经完全逆序,没有更大的
    if (index == 0) return null;
    // 2、把逆序区域刚刚大于他的数字交换位置
    exchangeHead(numbers, index);
    // 3、把原来的逆序区域转为正序
    reverse(numbers, index);
    return numbers;
  }

  /**
   * 找到数字逆序区域
   * @param numbers
   * @return
   */
  public static int findTransferPoint(int[] numbers){
    for (int i = numbers.length - 1; i > 0 ; i--) {
      if (numbers[i] > numbers[i - 1]){
        return i;
      }
    }
    return 0;
  }

  /**
   * 把逆序区域刚刚大于他的数字交换位置
   * @param numbers
   * @param index
   * @return
   */
  public static int[] exchangeHead(int[] numbers, int index){
    int head = numbers[index - 1];
    for (int i = numbers.length - 1; i > 0 ; i--) {
      if (head < numbers[i]){
        numbers[i - 1] = numbers[i];
        numbers[i] = head;
        break;
      }
    }
    return numbers;
  }

  /**
   * 逆序转为正序
   * @param numbers
   * @param index
   * @return
   */
  public static int[] reverse(int[] numbers, int index){
    for(int i = index, j = numbers.length - 1; i < j; i++, j--) {
      int temp = numbers[i];
      numbers[i] = numbers[j];
      numbers[j] = temp;
    }
    return numbers;
  }

  public static void main(String[] args) {
    int[] numbers = new int[]{1,2,3,4,5};

    System.out.println(Arrays.toString(findNearestNumber(numbers)));
  }
}


标题:寻找全排列的下一个数
作者:hymn
地址:https://dxyhymn.com/articles/2020/11/09/1604904335494.html