美文网首页
Leetcode--Two pointers

Leetcode--Two pointers

作者: Morphiaaa | 来源:发表于2017-06-09 02:57 被阅读0次

    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中相对应的位置也是空的,可以直接粘贴过去

    相关文章

      网友评论

          本文标题:Leetcode--Two pointers

          本文链接:https://www.haomeiwen.com/subject/wxdxqxtx.html