Sort Colors @ LeetCode (Python)
kitt
posted @ 2014年3月02日 21:52
in LeetCode
, 1854 阅读
要求只能扫一遍而且要in place, 只能通过交换A中的元素来实现。p0是指向0的指针, p2是指向2的指针, i是用于遍历的指针。如果当前元素A[i]是2, 则交换A[i]和A[p2]的值, 然后p2前移, i不动, 当i > p2就终止, 这样就排除了2的干扰，因为i前面的元素总是0或1。若A[i]是0, 交换A[i]和A[p0]的值, p0和i都后移, 若A[i]是1, 只要i后移即可, 换句话说, 总是把0往前放。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | class Solution: # @param A a list of integers # @return nothing, sort in place def sortColors(self, A): if A == []: return length = len(A); p0 = 0; p2 = length - 1 i = 0 while i <= p2: if A[i] == 2: A[p2], A[i] = A[i], A[p2] p2 -= 1 elif A[i] == 0: A[p0], A[i] = A[i], A[p0] p0 += 1 i += 1 else: i += 1 |
评论 (0)