47. 全排列 II

想着在原来全排列的基础上做个去重复的。。 结果时间复杂度上就上去了多了o(n)级别 = =

class Solution {
    func permuteUnique(_ nums: [Int]) -> [[Int]] {
        
        
        var ans = Array<Array<Int>>()
        
        let len = nums.count

        var useArray = Array.init(repeating: 0, count: len)
        var tempArray = Array.init(repeating: 0, count: len)

       dfs(0,nums,&useArray,&tempArray,&ans)
        
    
        return ans
    }
    func dfs(_ index:Int,_ nums:[Int],_ useArray:inout Array<Int>,_ tempArray: inout Array<Int>,_ ans: inout [[Int]]){
        
        let len = nums.count
        if index == len {
            let temp = Array.init(tempArray)
            if !ans.contains(temp){
                ans.append(temp)
            }
            return
        }
        //每一层可以选择的
        for i in 0..<len {
            
            if useArray[i] == 0 {
                tempArray[index] = nums[i]
                useArray[i] = 1
                dfs(index + 1,nums,&useArray,&tempArray,&ans)
                useArray[i] = 0
            }
        }
        
        
        
    }
}

优化版本1 通过省去了成员变量 速度提升了一点。但是还是不太好。应该在结果出来之前进行过滤。而不是最后

func permuteUnique(_ nums: [Int]) -> [[Int]] {
        
        
        var ans = Array<Array<Int>>()
        var temp = nums

       dfs(0,&temp,&ans)
        
    
        return ans
    }
    func dfs(_ index:Int,_ nums: inout [Int],_ ans: inout [[Int]]){
        
        let len = nums.count
        if index == len {
            let temp = Array.init(nums)
            if !ans.contains(temp){
                ans.append(temp)
            }
            return
        }
        //每一层可以选择的
        for i in index..<len {
            
            nums.swapAt(index, i)
            dfs(index + 1,&nums,&ans)
            nums.swapAt(index, i)
           
        }
        
        
        
    }

优化版本2

func permuteUnique(_ nums: [Int]) -> [[Int]] {
            
            
            var ans = Array<Array<Int>>()
            var temp = nums

           dfs(0,&temp,&ans)
            
        
            return ans
        }
        func dfs(_ index:Int,_ nums: inout [Int],_ ans: inout [[Int]]){
            
            let len = nums.count
            if index == len {
                ans.append(Array.init(nums))

                return
            }
            //每一层可以选择的
            for i in index..<len {
                if isRepeat(nums, index, i) {
                    continue
                }
                nums.swapAt(index, i)
                dfs(index + 1,&nums,&ans)
                nums.swapAt(index, i)
               
            }
            
        }
        
        func isRepeat(_ nums:[Int],_ index:Int, _ i:Int) -> Bool{
            
            for j in index..<i {
                if nums[j] == nums[i] {
                    return true
                }
            }
            
            return false

        }