leetcode_60

淳属虚构 · · 886 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

Golang:

思路：最直白的思路自然是递归把所有解都拿出来，然后找到第k个，或者递归到第k个为止，但这么做这题就没有灵魂了啊！！！所以，数学方法解才是我们追求的东西。代码不想解释了，数学方法，先得到第n位的值，再递归得第n-1位的值，直到结束。

代码如下：

func getPermutation(n int, k int) string {
    s:=""
    if n==0||k==0 {
        return s
    }
    arr:=make([]int,n+1)
    nums:=make([]int,n+1)
    temp:=1
    for i:=1;i<len(arr);i++ {
        temp=temp*i
        arr[i]=temp
    }
    getN(&s,nums,arr,n,k)
    return s
}
//取第n位的值
func getN(s *string,nums []int,arr []int,n int,k int){
    if k>arr[n] {
        return
    }
    if k==arr[n]||k==0 {
        for i:=len(nums)-1;i>0;i-- {
            if nums[i]==0 {
                *s=*s+strconv.Itoa(i)
                nums[i]=1
            }
        }
        return
    }
    if k>arr[n-1] {
        temp:=k/arr[n-1]
        k=k%arr[n-1]
        if k==0{
            temp=temp-1
        }
        flag:=0
        for i:=1;i<len(nums);i++ {
            if nums[i]==0 {
                if flag==temp {
                    *s=*s+strconv.Itoa(i)
                    nums[i]=1
                    break
                }else {
                    flag++
                }
            }
        }
    }else{
        for i:=1;i<len(nums);i++ {
            if nums[i]==0 {
                *s=*s+strconv.Itoa(i)
                nums[i]=1
                break
            }
        }
    }
    getN(s,nums,arr,n-1,k)
}

有疑问加站长微信联系（非本文作者）