Leetcode--Two pointers

2017-06-09  本文已影响0人  Morphiaaa

11. Container With Most Water

Brute force解法是针对每一个左边竖线,计算所有它形成的container的大小,最后找出最大的那个
Time complexity: O(n^2)
Two pointers 解法:left 从0开始,right从最后一个元素开始,先将此时的containter看为是最大的,然后比较两条竖线的大小,哪边小就更新哪边的指针。主要是因为container大小是有较小的那条线来决定的。
Time complexity: O(n)

88. Merge Sorted Array

用两个指针分别指向两个sorted array的末尾,从末尾的元素开始比较,将更大的那个元素放在nums1最后边,注意此时nums1的长度已经更新了:nums1[m+n -1],同时将指针向前移动一位。
循环条件是while m > 0 and n > 0:,因为nums1的长度足够大可以容纳m+n, 所以当循环结束后,n很有可能还大于0,这时要把nums2中剩下的部分直接放在nums1中相应的位置:
if n>0: nums1[:n] = nums2[:n],因为一开始我们就给nums1分配了m+n大小,所以当nums1循环完了而nums2还有剩余时,nums1中相对应的位置也是空的,可以直接粘贴过去

上一篇下一篇

猜你喜欢

热点阅读