博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
60. Permutation Sequence
阅读量:6571 次
发布时间:2019-06-24

本文共 3344 字,大约阅读时间需要 11 分钟。

一、题目

  1、审题

  2、分析

    给两个数字 n 与 k,返回 1-n 所有数字组成的从小到大的全排序的第 k 个数。

 

二、解答

  1、思路:

    方法一、采用字典序列,返回全部序列后,输出第 k 个。(时间超出,但代码可行)

public String getPermutation(int n, int k) {                Integer num = 0;        int i = 1;        while(i <= n)             num = num*10 + i++;                List
result = new ArrayList<>(); result.add(num.toString()); helper(result, new StringBuffer().append(num), n-1, n); for(String s: result) System.out.println(s); System.out.println(); return result.get(k-1).toString(); } private void helper(List
result, StringBuffer sb, int index, int len) { if(index < 0) return; // 1、查找比 index 大的最小的数的 index int tmpIndex = -1; for(int i = len - 1; i > index; i--) { if(sb.charAt(i) > sb.charAt(index)) { tmpIndex = i; break; } } if(tmpIndex != -1) { // 交换字符 char c = sb.charAt(tmpIndex); sb.setCharAt(tmpIndex, sb.charAt(index)); sb.setCharAt(index, c); // 2、 翻转 index 后面部分 String s = sb.substring(index+1); StringBuffer tmpBuffer = new StringBuffer(s).reverse(); // add sb.delete(index+1, len) .append(tmpBuffer.toString()); result.add(sb.toString()); helper(result, sb, len-2, len); } else { helper(result, sb, index - 1, len); } }

 

  方法二、采用数学的思维方法: 

    以   n = 4, k = 9 为例:

    ①、总共有 n! = 4!=4 X 3! = 24种排序。可以分为:

      1 和 {2, 3,  4} 

      2 和 {1, 3, 4}

      3 和 {1, 2, 4}

      4 和 {1,2,3}

     的排序。

    ② 对于数组 nums = {1, 2, 3, 4},要确定第一个数字的下标,则 

        K = 8 ;(由于排序的集合开始的下标是0,所以 K = 9 -1 = 8;)

        index = K/ (n-1)! = 8 / (4-1)! = 8/6 = 1; 即确定第一个数字: nums[1] = 2

    ③、由 ① 知,确定了第一个数字 2,即排除了数字 1 开始的所有排序,则剩下的待确定的 K 为:

        K = K - index * (n - 1)! = 8 - 1*(4-1)! = 8 - 6 = 2

      于是: index = K /( n - 2)! = 2 / 2! = 1 ,

      则,对于数组 nums = {1, 3, 4} ,确定了数字 nums[1] = 3;

    ④ 同理:

         K = K - index*(n-2)! = 2 - 1*(4-2)! = 0;

        index = K/(n-3)! = 0 / (n - 3)! = 1 / 1 = 0;

        则对于数组 nums = {1, 4}, 确定了数字 nums[0] = 1;

    ⑤

        K = K - Index * (n - 3)! = 0 - 0 * 1 = 0

        Index = 0 /(n-4)! = 0

        则对于数组 nums = {4},确定了数字 nums[0] = 4

  综上,对于  n = 4, k = 9 的排序为: 2314.

 

class Solution {    public String getPermutation(int n, int k) {                        List
numbers = new LinkedList
(); int[] factorial = new int[n+1]; StringBuilder sb = new StringBuilder(); // factorial[] = {1, 1, 2, 6, ... , n!} int sum = 1; factorial[0] = 1; for(int i = 1; i <= n; i++) { sum *= i; factorial[i] = sum; } // list = {1, 2, 3, 4} , get indices for (int i = 1; i <= n; i++) { numbers.add(i); } k--; for(int i = 1; i <= n; i++) { int index = k / factorial[n-i]; sb.append(numbers.remove(index)); k -= index*factorial[n-i]; } return String.valueOf(sb); }}

 

转载于:https://www.cnblogs.com/skillking/p/9668588.html

你可能感兴趣的文章
MySQL用户操作和数据的导出导入
查看>>
监听器实现案例----自定义session扫描器和统计在线用户人数及用户信息
查看>>
AutoCompleteTextView不能使用的问题
查看>>
使用git自动将子工程发布到百度开放云上
查看>>
【数学水题】【TOJ4113】【 Determine X】
查看>>
Swift 类型嵌套
查看>>
Mybatis_HelloWorld
查看>>
WCF - REST服务
查看>>
Linux Source命令及脚本的执行方式解析
查看>>
跟随我在oracle学习php(44)
查看>>
Spring集成hibernate错误
查看>>
实验四主存空间的分配和回收
查看>>
QtCreator常用快捷键
查看>>
一、javaSE (二十五)网络编程
查看>>
Oracle 10g安装报错记录
查看>>
JS 判断语句
查看>>
自定义网站根目录
查看>>
[WARNING]: Could not match supplied host pattern, ignoring: servers
查看>>
微信公众平台图文教程(三)消息管理和用户管理
查看>>
查找表中多余的重复记录(多个字段)
查看>>