C++实现LeetCode(60.序列排序)

[LeetCode] 60. Permutation Sequence 序列排序

The set [1,2,3,...,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

Given n and k, return the kth permutation sequence.

Note:

  • Given n will be between 1 and 9 inclusive.
  • Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

这道题是让求出n个数字的第k个排列组合，由于其特殊性，我们不用将所有的排列组合的情况都求出来，然后返回其第k个，这里可以只求出第k个排列组合即可，那么难点就在于如何知道数字的排列顺序，首先要知道当 n = 3 时，其排列组合共有 3! = 6 种，当 n = 4 时，其排列组合共有 4! = 24 种，这里就以 n = 4, k = 17 的情况来分析，所有排列组合情况如下：

1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412 <--- k = 17
3421
4123
4132
4213
4231
4312
4321

可以发现，每一位上 1,2,3,4 分别都出现了6次，当最高位上的数字确定了，第二高位每个数字都出现了2次，当第二高位也确定了，第三高位上的数字都只出现了1次，当第三高位确定了，那么第四高位上的数字也只能出现一次，下面来看 k = 17 这种情况的每位数字如何确定，由于 k = 17 是转化为数组下标为 16：

最高位可取 1,2,3,4 中的一个，每个数字出现 3！= 6 次（因为当最高位确定了，后面三位可以任意排列，所以是 3！，那么最高位的数字就会重复 3！次），所以 k = 16 的第一位数字的下标为 16 / 6 = 2，在 "1234" 中即3被取出。这里的k是要求的坐标为k的全排列序列，定义 k' 为当最高位确定后，要求的全排序列在新范围中的位置，同理，k'' 为当第二高为确定后，所要求的全排列序列在新范围中的位置，以此类推，下面来具体看看：

第二位此时从 1,2,4 中取一个，k = 16，则此时的 k' = 16 % (3!) = 4，注意思考这里为何要取余，如果对这 24 个数以6个一组来分，那么 k=16 这个位置就是在第三组（k/6 = 2）中的第五个（k%6 = 4）数字。如下所示，而剩下的每个数字出现 2！= 2 次，所以第二数字的下标为 4 / 2 = 2，在 "124" 中即4被取出。

3124
3142
3214
3241
3412 <--- k' = 4
3421

第三位此时从 1,2 中去一个，k' = 4，则此时的 k'' = 4 % (2!) = 0，如下所示，而剩下的每个数字出现 1！= 1 次，所以第三个数字的下标为 0 / 1 = 0，在 "12" 中即1被取出。

3412 <--- k'' = 0
3421

第四位是从2中取一个，k'' = 0，则此时的 k''' = 0 % (1!) = 0，如下所示，而剩下的每个数字出现 0！= 1 次，所以第四个数字的下标为 0 / 1= 0，在 "2" 中即2被取出。

3412 <--- k''' = 0

那么就可以找出规律了
a1 = k / (n - 1)!
k1 = k

a2 = k1 / (n - 2)!
k2 = k1 % (n - 2)!
...

an-1 = kn-2 / 1!
kn-1 = kn-2 % 1!

an = kn-1 / 0!
kn = kn-1 % 0!

代码如下：

class Solution {
public:
    string getPermutation(int n, int k) {
        string res;
        string num = "123456789";
        vector<int> f(n, 1);
        for (int i = 1; i < n; ++i) f[i] = f[i - 1] * i;
        --k;
        for (int i = n; i >= 1; --i) {
            int j = k / f[i - 1];
            k %= f[i - 1];
            res.push_back(num[j]);
            num.erase(j, 1);
        }
        return res;
    }
};

到此这篇关于C++实现LeetCode(60.序列排序)的文章就介绍到这了,更多相关C++实现序列排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(58.求末尾单词的长度)

    [LeetCode] 58. Length of Last Word 求末尾单词的长度 Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string. If the last word does not exist, return 0. Note: A word is defined as a

  • C++实现LeetCode(59.螺旋矩阵之二)

    [LeetCode] 59. Spiral Matrix II 螺旋矩阵之二 Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order. Example: Input: 3 Output: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] 此题跟之前那道 Spiral Matrix 本质上没什么区别,就相当于个类似逆

  • C++实现LeetCode(56.合并区间)

    [LeetCode] 56. Merge Intervals 合并区间 Given a collection of intervals, merge all overlapping intervals. Example 1: Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into

  • C++实现LeetCode(61.旋转链表)

    C++实现LeetCode(61.旋转链表)

    [LeetCode] 61. Rotate List 旋转链表 Given the head of a linked list, rotate the list to the right by k places. Example 1: Input: head = [1,2,3,4,5], k = 2 Output: [4,5,1,2,3] Example 2: Input: head = [0,1,2], k = 4 Output: [2,0,1] Constraints: The number

  • C++实现LeetCode(57.插入区间)

    [LeetCode] 57. Insert Interval 插入区间 Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times. Example 1: Input: int

  • C++实现LeetCode(189.旋转数组)

    [LeetCode] 189. Rotate Array 旋转数组 Given an array, rotate the array to the right by k steps, where k is non-negative. Example 1: Input: [1,2,3,4,5,6,7] and k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate

  • C++实现LeetCode(60.序列排序)

    [LeetCode] 60. Permutation Sequence 序列排序 The set [1,2,3,...,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, we get the following sequence for n = 3: "123" "132" "213" &

  • C++实现LeetCode(769.可排序的最大块数)

    [LeetCode] 769.Max Chunks To Make Sorted 可排序的最大块数 Given an array arr that is a permutation of [0, 1, ..., arr.length - 1], we split the array into some number of "chunks" (partitions), and individually sort each chunk.  After concatenating them,

  • C++实现LeetCode(768.可排序的最大块数之二)

    [LeetCode] 768.Max Chunks To Make Sorted II 可排序的最大块数之二 This question is the same as "Max Chunks to Make Sorted" except the integers of the given array are not necessarily distinct, the input array could be up to length 2000, and the elements cou

  • C++实现LeetCode(75.颜色排序)

    [LeetCode] 75. Sort Colors 颜色排序 Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2

  • C++实现LeetCode(148.链表排序)

    [LeetCode] 148. Sort List 链表排序 Sort a linked list in O(n log n) time using constant space complexity. Example 1: Input: 4->2->1->3 Output: 1->2->3->4 Example 2: Input: -1->5->3->4->0 Output: -1->0->3->4->5 常见排序方法有

  • python sort、sorted高级排序技巧

    Python list内置sort()方法用来排序,也可以用python内置的全局sorted()方法来对可迭代的序列排序生成新的序列. 1)排序基础 简单的升序排序是非常容易的.只需要调用sorted()方法.它返回一个新的list,新的list的元素基于小于运算符(__lt__)来排序. 复制代码 代码如下: >>> sorted([5, 2, 3, 1, 4]) [1, 2, 3, 4, 5] 你也可以使用list.sort()方法来排序,此时list本身将被修改.通常此方法不如s

  • 算法之排序算法的算法思想和使用场景总结

    1. 概述 排序算法是计算机技术中最基本的算法,许多复杂算法都会用到排序.尽管各种排序算法都已被封装成库函数供程序员使用,但了解排序算法的思想和原理,对于编写高质量的软件,显得非常重要. 本文介绍了常见的排序算法,从算法思想,复杂度和使用场景等方面做了总结. 2. 几个概念 (1)排序稳定:如果两个数相同,对他们进行的排序结果为他们的相对顺序不变.例如A={1,2,1,2,1}这里排序之后是A = {1,1,1,2,2} 稳定就是排序后第一个1就是排序前的第一个1,第二个1就是排序前第二个1,第

  • c++中八大排序算法

    c++中八大排序算法

    概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 我们这里说说八大排序就是内部排序. 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序.堆排序或归并排序序. 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短:  1.插入排序-直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入

  • Python排序搜索基本算法之归并排序实例分析

    Python排序搜索基本算法之归并排序实例分析

    本文实例讲述了Python排序搜索基本算法之归并排序.分享给大家供大家参考,具体如下: 归并排序最令人兴奋的特点是:不论输入是什么样的,它对N个元素的序列排序所用时间与NlogN成正比.代码如下: # coding:utf-8 def mergesort(seq): if len(seq)<=1: return seq mid=int(len(seq)/2) left=mergesort(seq[:mid]) right=mergesort(seq[mid:]) return merge(lef

  • python中sort和sorted排序的实例方法

    Python list内置sort()方法用来排序,也可以用python内置的全局sorted()方法来对可迭代的序列排序生成新的序列. 1)排序基础 简单的升序排序是非常容易的.只需要调用sorted()方法.它返回一个新的list,新的list的元素基于小于运算符(__lt__)来排序. >>> sorted([5, 2, 3, 1, 4]) [1, 2, 3, 4, 5] 你也可以使用list.sort()方法来排序,此时list本身将被修改.通常此方法不如sorted()方便,但

随机推荐