LeetCode42 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
对于每个柱子，找到它左右两边最高的柱子，它所能容纳的雨水为min(max_left, max_- right) - height,时间空间复杂度都为O(n),

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        m = len(height)
        max_left,max_right = [0]*m,[0]*m
        l,r = 0,0
        for i in range(m):
            if l<height[i]:
                l = height[i]
            max_left[i] = l
            if r<height[m-1-i]:
                r = height[m-1-i]
            max_right[m-1-i] = r
        res=0
        for i in range(m):
            res += min(max_left[i],max_right[i])-height[i]
        return res

LeetCode41 缺失的第一个正数

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。

思路
举个例子:最小的正数有可能是1,2,3,…..,最大是n+1,遍历数组，假设1出现了，就将1放到nums[0],2出现就放在nums[1]，依次类推，等遍历完这次数组，“正确的数字都放到了正确的位置”，所以，再次遍历数组，找出第一个数字与位置不对应的”位置”。

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(len(nums)):
            while nums[i] != i+1:
                if nums[i]<=0 or nums[i]>len(nums) or nums[i] == nums[nums[i]-1]:
                    break
                j = nums[i]
                nums[i],nums[j-1] = nums[j-1],nums[i]
        for i in range(len(nums)):
            if nums[i] != i+1:
                return i+1
        return len(nums)+1

LeetCode442. 数组中重复的数据

给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。找到所有出现两次的元素。
你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？

把“正确”的数放到“正确”的位置，有重复的数字将在“错误的位置”，最后找到这样“错误的”数。

class Solution(object):
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        if n<=1:return []
        res = []
        i = 0
        while i<n:
            idx = nums[i]-1
            if nums[idx] != nums[i]:
                nums[idx],nums[i] = nums[i],nums[idx]
            else: i += 1
        i = 0
        while i<n:
            if nums[i] != i+1:
                res.append(nums[i])
            i += 1
        return res

LeetCode448. 找到所有数组中消失的数字

给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。

class Solution(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        i,res = 0,[]
        while i<n:
            idx = nums[i]-1
            if nums[i]!=nums[idx]:
                nums[i],nums[idx] = nums[idx],nums[i]
            else: i += 1
        for i in range(n):
            if nums[i] != i+1:
                res.append(i+1)
        return res