For example, given k = 3,
Return [1,3,3,1].
Note:
Could you optimize your algorithm to use only O(k) extra space?
Idea: Pascal triangle is a problem taught in middle school. So I think it is OK to use the generation equation.
The n'th row: [combination(n, 0), combination(n, 1), combination(n, 2),..., combination(n, n)], where combination(n, k+1) = combination(n, k)*(n-k)/(k+1).
Time: O(n) Space: O(1)
Code:
public class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> result=new ArrayList<Integer>();
long value=1;
for(int k=0;k<=rowIndex;k++)
{
result.add((int)value);
value=value*(rowIndex-k)/(k+1);
}
return result;
}
}
No comments:
Post a Comment