Hexo

##LeetCode485

方法一：一次遍历

算法：

用一个计数器 count 记录 1 的数量，另一个计数器 maxCount 记录当前最大的 1 的数量。
遇到 1 时，count 加一。遇到 0 时：将 count 与 maxCount 比较，maxCoiunt 记录较大值。
将 count 设为 0。 返回 max（Count，maxcount)。

PS :当然也可以在遇到1时候就进行maxcount比较，（从测试用例耗时来看）和前面相比耗时会多一些 ，考虑原因可能是题目是找最大连续1的个数，用例中1比0多的用例占多数，遇到0时再max比较，比较次数会少一些

def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
       res=0
       count=0
       for i in range(len(nums)):
           if nums[i]:
               count+=1
               #res=max(res,count)
           else:
               count=0
               res=max(res,count)
       #return res
   	retuen max(res,count)

复杂度分析

时间复杂度：O(N) N是数组的长度。
空间复杂度：O(1) count 和 maxCount。
方法二：
使用 splits 函数在 0 处分割将数组转换成字符串。在获取子串的最大长度就是最大连续 1 的长度。

return max(map(len, ''.join(map(str, nums)).split('0'))

方法三：

看到评论区有其他语言的双指针法，改写python

class Solution(object):
    def findMaxConsecutiveOnes(self, nums):
        count =0
        start = 0
        for i in range(len(nums)):
            if nums[i]==1:
                start =i
                break
        curstart = start 
        maxcount = 0
        count =0
        for i in range(start, len(nums)):
            if nums[i]==1:
                count+=1
                if count>maxcount:
                    maxcount = count
            else:
                curstart=i+1
                count = 0
        return maxcount

如果使用普通的快排划分，虽然时间复杂度是O(n)，空间复杂度是O(1)。

但是仍然不是最优解。因为普通的快排划分需要对数组进行两次扫描(第一次以2为中心划分，第二次以1为中心划分)。

题目要求的最优是对数组进行一次扫描。

怎么做呢？

设置两个变量r1,r2，含义是r1,左边(包含r1)的变量值都小于1，r2左边(包含r2)的变量值都小于2。

那么初始时他俩都是-1(实际上是左边界-1)，代表他俩所包裹的范围是空。

假设现在有数组nums = [0,0,1,1,2,0,0],r1 = 1,r2 = 3。下一个数组索引i是5，也就是要处理0，这个数是小于2的。

因此r2+1，代表区间扩大，把nums[i]和nums[r2]交换。此时维持了r2左侧的数都是小于2的这个性质。

交换完之后，这个小于2的数存放在了nums[r2]，但是这个nums[r2]仍然有可能小于1，若是小于1，那么

应该把r1+1，代表区间扩大，然后把nums[r1]和nums[r2]交换，这样才能维持r1左侧的数小于1的这个性质。

def sortColors(self, nums: List[int]) -> None:
        def swap(nums,i,j):
            temp=nums[i]
            nums[i]=nums[j]
            nums[j]=temp
        r1,r2=-1,-1
        for i in range (len(nums)):
            if nums[i]<2:
                r2+=1
                swap(nums,i,r2)
                if nums[r2]<1:
                    r1+=1
                    swap(nums,r1,r2)

赏

×

纯属好玩

扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦