题目描述

输入一组数字（可能包含重复数字），输出其所有的排列方式。

样例

输入：[1,2,3]

输出：
      [
        [1,2,3],
        [1,3,2],
        [2,1,3],
        [2,3,1],
        [3,1,2],
        [3,2,1]
      ]

golang 代码

/*
//数字全部不重复
//思想：n个数字，先对n-1个进行排序，再把第n个数字插入n-1排序的切片里
func permutation(nums []int) [][]int {
    return order(nums)
}

//求出所有n个元素排序
func order(nums []int) [][]int {
    if len(nums) == 0 {
        return nil
    }
    if len(nums) == 1 {
        temp := make([][]int, 1)
        temp[0] = nums
        return temp
    }
    //将第n个元素插入到前n-1个元素的队列里
    return insert(order(nums[:len(nums)-1]), nums[len(nums)-1]) 
}

//例如输入 [[1,2],[2,1]]   3        需要返回[[1,2,3], ... ]
func insert(nums [][]int, insertnum int) [][]int {
    var ans [][]int
    for _ , n := range nums {
        for i := 0 ; i < len(n) ; i++ {
            var temp = make([]int,len(n))
            _ = copy(temp, n)
            temp = append(temp[:i], insertnum)
            temp = append(temp,n[i:]...)
            ans = append(ans,temp)
        }
        temp := append(n, insertnum)
        ans = append(ans,temp)
    }
    return ans
}
*/

//数字重复，重复的数字只能放到另一个数字之后
func permutation(nums []int) [][]int {
    //排序
    mysort(nums)
    return order(nums)
}

//冒泡
func mysort(nums []int) {
    for i := 0 ; i < len(nums) - 1 ; i++ {
        for j := i + 1 ; j < len(nums) ; j++ {
            if nums[i] > nums[j] {
                nums[i],nums[j] = nums[j],nums[i]
            }
        }
    }
}

func order(nums []int) [][]int {
    if len(nums) == 0 {
        return nil
    }
    if len(nums) == 1 {
        temp := make([][]int, 1)
        temp[0] = nums
        return temp
    }
    return insert(order(nums[:len(nums)-1]), nums[len(nums)-1])
}

func insert(nums [][]int , insertnum int) [][]int {
    var ans [][]int
    for _, n := range nums {
        var pre = -1
        //存在相等数就添加后面，不存在则从头开始添加
        for k := len(n)-1 ; k >= 0 ; k-- {
            if n[k] == insertnum {
                pre = k
                break
            }
        }
        for i := pre + 1 ; i < len(n) ; i++ {
            var temp = make([]int , len(n))
            _ = copy(temp, n)
            temp = append(temp[:i],insertnum)
            temp = append(temp, n[i:]...)
            ans = append(ans,temp)
        }
        temp := append(n,insertnum)
        ans = append(ans,temp)
    }
    return ans
}