119. 杨辉三角 II

【问题描述】
给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。

PascalTriangleAnimated2.gif

【示例】

输入: 3
输出: [1,3,3,1]

【进阶】

你可以优化你的算法到 O(k) 空间复杂度吗？

根据题目1 可得出解法1

• 时间复杂度O(nlogn)
• 空间复杂度O(n+k)
  【解1】

func getRow(_ rowIndex: Int) -> [Int] {
    if rowIndex == 0 {
        return [1]
    } else if rowIndex == 1 {
        return [1,1]
    } else {
        var arr = [[Int]]()
        arr.append([1])
        arr.append([1,1])
        for num in 2...rowIndex {
            var tmp = [Int]()
            let preArr = arr[num-1]
            for i in 0...num {
                if i == 0 || i == num {
                    tmp.append(1)
                } else {
                    tmp.append(preArr[i]+preArr[i-1])
                }
            }
            arr.append(tmp)
        }
        return arr[rowIndex]
    }
}

解法2

• 空间复杂度O(k)
• 时间复杂度O(nlogn)
  【解2】

func getRow(_ rowIndex: Int) -> [Int] {
    var result = Array.init(repeating: 0, count: rowIndex+1)
    result[0] = 1
    for i in 0...rowIndex {
        var tmp = i
        while tmp > 0 {
            result[tmp]+=result[tmp-1]
            tmp-=1
        }
    }
    return result
}

思路：

• 因为只需要返回给定行数数组即可，不需要保留整个数组
• 所以只需要一直迭代循环即可，需要给出边界为0的值
• 当rowIndex=0,return [1]