首页 » 技术分享 » 每日编程(二十三)--strings.Builder的使用

每日编程(二十三)--strings.Builder的使用

 

题目:第k个排列

题目描述:
给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:

“123”
“132”
“213”
“231”
“312”
“321”
给定 n 和 k,返回第 k 个排列。

说明:

给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。
示例 1:

输入: n = 3, k = 3
输出: “213”
示例 2:

输入: n = 4, k = 9
输出: “2314”

分析:这就是一道数学的排列组合的题,我尽力解释清楚,首先明确的就是n决定这最后返回数的位数,再来明确几个算术,n个数排列组合一共有n!种排列方法,相同数字开头的有(n-1)!种,所以很明显我们要根据k与(n-1)!的关系来确定每一位上的数字是什么
举例说明:
n=3;k=3;
sum=n!=6
首先确定第一位:
k%(n-1)!=1 ==》说明第一位是第二组的数,也就是是第二大数开头的 也就是2
n=n-2=1
确定第二位:
k%(n-2)!=0 ==》说明第二位就是最小的数了,也就是1
n=n-3=0
确定第三位:
剩下的那个就是最后一位了
代码:

func getPermutation(n int, k int) string {
    var result strings.Builder
    org :=make([]int,0)
    num :=1
    for i:=1;i<=n;i++{
        org=append(org,i)
        num *=i
    }
    cur:=0
    for i:=0;i<n;i++{
        num /=n-i
        if k%num==0{
            cur=k/num-1
        }else{
            cur=k/num
        }
        result.WriteString(strconv.Itoa(org[cur]))
        org=append(org[:cur],org[cur+1:]...)
        k -= cur*num
    }
    return result.String()
}

我采用的是strings包,strings.Builder 创建一个string类型的数值写入builder中,Builder的底层实现其实就是一个string类型的切片,所以当执行WriteString操作时,实际上就是append操作,最后利用String()函数将他拼接成一个字符串,非常高效。

转载自原文链接, 如需删除请联系管理员。

原文链接:每日编程(二十三)--strings.Builder的使用,转载请注明来源!

0