Leetcode题解 - 数组

本系列为Leetcode刷题笔记，刷题平台为Leetcode中文站，刷题按Tag分类。本系列题解汇总如下 (持续更新…)：

本文主要是数组相关题目题解总结。

[TOC]

1. 两数之和

题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if len(nums) <= 1:
            return False
        Dict = {}
        
        for i in range(len(nums)):
            if target-nums[i] in Dict:
                return [Dict[target-nums[i]], i]
            else:
                Dict[nums[i]] = i
        
        return False

4. 寻找两个有序数组的中位数

题目描述

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0
示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

解题思路

• 复杂度$O(log(m + n))$方法待续。。。

• 归并排序。复杂度为$O((m+n)log(m+n))$，不符合。

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        
        if len(nums1) == 0 and len(nums2) == 0:
            return 0
        
        res = []
        i, j = 0, 0
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                res.append(nums1[i])
                i += 1
            else:
                res.append(nums2[j])
                j += 1
        if i != len(nums1):
            res.extend(nums1[i:])
        else:
            res.extend(nums2[j:])
        
        if len(res) % 2:
            return res[len(res)//2]
        else:
            return (res[len(res)//2-1] + res[len(res)//2]) / 2.0

11. 盛最多水的容器

题目描述

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

解题思路

双指针法，一个从前往后，一个从后往前，计算两个挡板之间的面积，然后向中间移动，那个挡板比较矮，就舍弃这个挡板。

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if height <= 1:
            return False
        
        res = 0
        left, right = 0, len(height)-1
        while left < right:
            temp = (right-left)*min(height[left], height[right])
            if temp > res:
                res = temp
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        
        return res

15. 三数之和

题目描述

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解题思路

先对数组进行排序，然后遍历数组，对每个位置都从它的后一个元素到末尾取两个元素加和，如果为0就添加到结果数组中。需要跳过相同的数字。

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) <= 2:
            return []
        
        nums.sort()
        
        res = []
        for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            left, right = i+1, len(nums)-1
            while left < right:
                if nums[i] + nums[left] + nums[right] == 0:
                    res.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left-1]:
                        left += 1
                    while right > left and nums[right] == nums[right+1]:
                        right -= 1
                elif nums[i] + nums[left] + nums[right] > 0:
                    right -= 1
                else:
                    left += 1
        
        return res

16. 最接近的三数之和

题目描述

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

解题思路

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if len(nums) <= 2:
            return 0
        
        nums.sort()
        res = float('inf')
        for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            left, right = i+1, len(nums)-1
            while left < right:
                temp = nums[i]+nums[left]+nums[right]
                if abs(temp-target) < abs(res-target):
                    res = temp
                if temp == target:
                    return target
                elif temp < target:
                    left += 1
                else:
                    right -= 1
        
        return res

18. 四数之和

题目描述

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

解题思路

先对数组进行排序，使用字典保存每两个元素和的下标组成的元祖，例如[1,2,2,3]，Dict={3:[(0,1),(0,2)], 4:[(0,3),(1,2)], 5:[(2,3)]}，然后对数组进行两层遍历，判断target-nums[i]-nums[j]在不在字典中，如果在字典中，则找到了一组解。由于需要去重，使用set()类型的数据结构。

class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if len(nums) < 4:
            return []
        
        nums.sort()
        Dict = {}
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i]+nums[j] not in Dict:
                    Dict[nums[i]+nums[j]] = [(i, j)]
                else:
                    Dict[nums[i]+nums[j]].append((i, j))
        
        res = set()
        for i in range(len(nums)):
            for j in range(i+1, len(nums)-2):
                residue = target-nums[i]-nums[j]
                if residue in Dict:
                    for pair in Dict[residue]:
                        if pair[0] > j:
                            res.add((nums[i], nums[j], nums[pair[0]], nums[pair[1]]))

        return list(res)

首先做排序，对前两个数遍历，后两个数在剩下的区间内寻找，找的方式使用两个指针指向首尾，判断四个数组成的和是否为target。注意需要在移动过程中去重。(超出时间限制)

class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if len(nums) < 4:
            return []
        
        nums.sort()
        res = []
        n = len(nums)
        for i in range(n-3):
            if (i > 0 and nums[i] == nums[i-1]) or nums[i]+nums[n-3]+nums[n-2]+nums[n-1] < target:
                continue
            if nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target:
                break
            for j in range(i+1, n-2):
                if (j > i+1 and nums[j] == nums[j-1]) or nums[i]+nums[j]+nums[n-2]+nums[n-1] < target:
                    continue
                if nums[i]+nums[j]+nums[j+1]+nums[j+2] > target:
                    break
                left, right = j+1, n-1
                while left < right:
                    temp = nums[i]+nums[j]+nums[left]+nums[right]
                    if temp == target:
                        res.append([nums[i],nums[j],nums[left],nums[right]])
                        left += 1
                        right -= 1
                        while left < right:
                            if nums[left] == nums[left-1]:
                                left += 1
                        while left < right:
                            if nums[right] == nums[right+1]:
                                right -= 1
                    elif temp > target:
                        right -= 1
                    else:
                        left += 1
        return res

26. 删除排序数组中的重复项

题目描述

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

解题思路

双指针。第一个指向当前不重复的位置len，另一个不断向后遍历遇到不重复的就写到len位置。

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

27. 移除元素

题目描述

给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,1,2,2,3,0,4,2], val = 2,

函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

注意这五个元素可为任意顺序。

你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

解题思路

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        
        i = 0
        for j in range(len(nums)):
            if nums[j] != val:
                nums[i] = nums[j]
                i += 1
        
        return i

31. 下一个排列

题目描述

解题思路

先找到从后面开始数第一个降序的位置，在将这个位置之后的数字翻转，然后遍历翻转的部分数字，最后交换这个降序数字和后面第一个比他大的数。

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        
        if len(nums) < 2:
            return
        
        index = len(nums) - 2
        while index >= 0:
            if nums[index] < nums[index+1]: #从后找到第一个降序数字
                break
            index -= 1
        
        nums[index+1:] = nums[index+1:][::-1] #将降序数字后面的数字翻转
        
        for i in range(index+1, len(nums)):
            if nums[i] > nums[index]: #在翻转的数字中找到第一个大于降序数字的
                nums[i], nums[index] = nums[index], nums[i] #交换
                break

class Solution {
    public void nextPermutation(int[] nums) {
        if (nums.length <= 1)
            return;
        int index = nums.length-1;
        while (index >= 1){
            if(nums[index] > nums[index-1])
                break;
            index --;
        }
        reverse(nums, index, nums.length-1);
        if (index == 0)
            return;

        for (int i=index; i<nums.length; i++){
            if (nums[i] > nums[index-1]){
                swap(nums, i, index-1);
                break;
            }
        }
        return;
    }
    public void reverse(int[] nums, int start, int end){
        while (start < end){
            swap(nums, start, end);
            start ++;
            end --;
        }
    }
    public void swap(int[] nums, int start, int end){
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
    }

}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        int [] nums = new int[]{3,2,1};
        sol.nextPermutation(nums);
        for (int i = 0; i < nums.length; i++)
            System.out.print(nums[i]);
    }
}

33. 搜索旋转排序数组

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

解题思路

双指针。

• 当nums[mid] == target时，返回mid；
• 当nums[mid] < nums[right]，则[mid,right]一定有序，判断target是否在(mid,right]中，如果在则left = mid+1，否则在另一段中，right = mid-1
• 当nums[mid] > nums[right]，则[left,mid]一定有序，判断target是否在[left,mid)中，如果在，则right=mid-1，否则，left = mid+1.

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if len(nums) == 0:
            return -1
        
        left, right = 0, len(nums)-1
        while left <= right:
            mid = left + (right-left)//2
            if nums[mid] == target:
                return mid
            
            if nums[mid] < nums[right]:
                if target > nums[mid] and target <= nums[right]:
                    left = mid+1
                else:
                    right = mid-1
            else:
                if target >= nums[left] and target < nums[mid]:
                    right = mid-1
                else:
                    left = mid+1
        
        return -1

41. 缺失的第一个正数

题目描述

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。

示例 1:

输入: [1,2,0]
输出: 3

示例 2:

输入: [3,4,-1,1]
输出: 2

示例 3:

输入: [7,8,9,11,12]
输出: 1

说明:
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。

解题思路

从第一个位置开始，让每个数字放在自己应该在的位置上，终止条件为一旦发现该位置的数字不应该出现在数组中（<=0或>len(nums)），则终止交换。
然后遍历数组，将第一个不符合要求的数字输出。

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        for i in range(len(nums)):
            while nums[i] > 0 and nums[i] <= len(nums) and nums[i] != nums[nums[i]-1]:
                temp = nums[nums[i]-1]
                nums[nums[i]-1] = nums[i]
                nums[i] = temp
                # nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i] 这样交换错误
                
        for i in range(len(nums)):
            if nums[i] != i+1:
                return i+1
        return len(nums)+1

42. 接雨水

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

解题思路

求最高点处的索引，从左往最高点遍历，从右往最高点遍历
遍历过程以初始点为最高点，当遇到比其低的点，则说明可以接水，接水量为两者之差，当遇到比其高的点，则更新当前最高点。

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        
        if len(height) < 3:
            return 0
        
        maxIndex = 0
        for i in range(1, len(height)):
            if height[i] > height[maxIndex]:
                maxIndex = i
        
        res = 0
        
        curMax = height[0]
        for i in range(1, maxIndex):
            if height[i] > curMax:
                curMax = height[i]
            else:
                res += curMax - height[i]

        curMax = height[-1]
        for i in range(len(height)-2, maxIndex, -1):
            if height[i] > curMax:
                curMax = height[i]
            else:
                res += curMax - height[i]
        
        return res

48. 旋转图像

题目描述

给定一个 n × n 的二维矩阵表示一个图像。

将图像顺时针旋转 90 度。

说明：

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例 1:

给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

原地旋转输入矩阵，使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

示例 2:

给定 matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

原地旋转输入矩阵，使其变为:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

解题思路

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        # 先沿着左上右下的对角线翻转
        for i in range(len(matrix)):
            for j in range(i+1, len(matrix)):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        
        #在翻转每一行
        for i in range(len(matrix)):
            matrix[i] = matrix[i][::-1]

54. 螺旋矩阵

题目描述

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

示例 2:

输入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

解题思路

从左到右，从上到下，从右到左，从下到上，循环。

class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        if len(matrix) == 0:
            return []
        
        top, buttom = 0, len(matrix)-1
        left, right = 0, len(matrix[0])-1
        res = []
        
        while top <= buttom and left <= right:
            
            for i in range(left, right+1):
                res.append(matrix[top][i])
            
            for i in range(top+1, buttom+1):
                res.append(matrix[i][right])
            
            if top < buttom: # 当top==buttom时，最后为一行，前面已经从左到右遍历过，不需重复遍历
                for i in range(right-1, left-1, -1):
                    res.append(matrix[buttom][i])
            
            if left < right: # 当left == right时， 最后为一列，前面已经从上到下遍历过了，不需重复遍历
                for i in range(buttom-1, top, -1):
                    res.append(matrix[i][left])
            
            top, buttom = top+1, buttom-1
            left, right = left+1, right-1
        
        return res

59. 螺旋矩阵 II

题目描述

给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3
输出:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

解题思路

class Solution(object):
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        if n == 0:
            return []
        if n == 1:
            return [[1]]
        
        matrix = [[0]*n for i in range(n)]
        
        top, buttom = 0, n-1
        left, right = 0, n-1
        val = 1
        
        while top <= buttom and left <= right:
            
            for i in range(left, right+1):
                matrix[top][i] = val
                val += 1
            
            for i in range(top+1, buttom+1):
                matrix[i][right] = val
                val += 1
            
            if top < buttom:
                for i in range(right-1, left-1, -1):
                    matrix[buttom][i] = val
                    val += 1
            
            if left < right:
                for i in range(buttom-1, top, -1):
                    matrix[i][left] = val
                    val += 1
            
            top, buttom = top+1, buttom-1
            left, right = left+1, right-1
        
        return matrix

73. 矩阵置零

题目描述

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

示例 1:

输入: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

示例 2:

输入: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

进阶:

• 一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
• 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
• 你能想出一个常数空间的解决方案吗？

解题思路

O(m+n)

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        
        row = [False] * len(matrix)
        col = [False] * len(matrix[0])
        
        # 找出0的位置 
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    row[i] = True
                    col[j] = True
        
        # 将0所在的行和列置0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if row[i] or col[j]:
                    matrix[i][j] = 0

将0所在的行或列的其他位置置为’#’，然后替换成0

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        
        if len(matrix) == 0:
            return 
        
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    for k in range(len(matrix[0])):
                        if matrix[i][k] != 0:
                            matrix[i][k] = '#'
                    for k in range(len(matrix)):
                        if matrix[k][j] != 0:
                            matrix[k][j] = '#'
        
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == '#':
                    matrix[i][j] = 0

74. 搜索二维矩阵

题目描述

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列。
• 每行的第一个整数大于前一行的最后一个整数。

示例 1:

输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
输出: true

示例 2:

输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
输出: false

解题思路

从左下角开始搜索

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if len(matrix) == 0:
            return False
        
        rows, cols = len(matrix)-1, len(matrix[0])-1
        i, j = rows, 0
        
        while i >= 0 and j <= cols:
            if matrix[i][j] == target:
                return True
            elif matrix[i][j] > target:
                i -= 1
            else:
                j += 1
        
        return False

81. 搜索旋转排序数组 II

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

示例 1:

输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true

示例 2:

输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false

进阶:

这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。
这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

解题思路

在每个while循环中，先将开头重复的和结尾重复的去掉。

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        if len(nums) == 0:
            return False
        
        left, right = 0, len(nums)-1
        while left <= right:
            val = nums[left]
            while left < right and nums[left+1] == val:
                left += 1
            val = nums[right]
            while left < right and nums[right-1] == val:
                right -= 1
                
            mid = left + (right-left)//2
            if nums[mid] == target:
                return True
            elif nums[mid] < nums[right]:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
            else:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left  = mid + 1
        return False

118. 杨辉三角

题目描述

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

解题思路

class Solution(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        if numRows == 0:
            return []
        
        res = [[1]]
        
        for i in range(2, numRows+1):
            pre = res[-1]
            
            temp = []
            i = 0
            while i < len(pre)-1:
                temp.append(pre[i]+pre[i+1])
                i += 1
            res.append([1]+temp+[1])
        
        return res

119. 杨辉三角 II

题目描述

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

输入: 3
输出: [1,3,3,1]

进阶：

• 你可以优化你的算法到 O(k) 空间复杂度吗？

解题思路

class Solution(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        if rowIndex == 0:
            return [1]
        
        res = [1]
        
        for i in range(2, rowIndex+2):
            temp = []
            for i in range(len(res)-1):
                temp.append(res[i]+res[i+1])
            res = [1]+temp+[1]
        
        return res

189. 旋转数组

题目描述

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

说明:

• 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
• 要求使用空间复杂度为 O(1) 的原地算法。

解题思路

切片，拼接

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        
        if k <= 0 or len(nums) == 0:
            return nums
        
        k = k%len(nums)
        
        nums[:] = nums[-k:]+nums[:-k]

先把所有的翻转，然后在对0~k和k~n分别进行翻转。

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        
        if k <= 0 or len(nums) == 0:
            return
        
        k = k%len(nums)
        
        self.reverse(nums, 0, len(nums)-1)
        self.reverse(nums, 0, k-1)
        self.reverse(nums, k, len(nums)-1)
    
    def reverse(self, nums, left, right):
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

209. 长度最小的子数组

题目描述

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。

示例:

输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

进阶:

如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

解题思路

双指针

class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        
        
        if len(nums) == 0:
            return 0
        
        res = float('inf')
        
        left, right = 0, 0
        
        while right < len(nums) and left <= right:
            if sum(nums[left:right+1]) >= s:
                res = min(res, right-left+1)
                left += 1
            else:
                right += 1
        
        return res if res!=float('inf') else 0

216. 组合总和 III

题目描述

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

• 所有数字都是正整数。
• 解集不能包含重复的组合。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

解题思路

class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        if n <= 0 or k <= 0 or n > 45:
            return []
        
        nums = [x for x in range(1, 10)]
        
        res = []
        self.dfs(nums, [], 0,  k, n, res)
        return res
    
    def dfs(self, nums, path, index, k, target, res):
        if k == 0 and target == 0 and path:
            res.append(path)
            return
        for i in range(index, len(nums)):
            if nums[i] > target:
                return
            self.dfs(nums, path+[nums[i]], i+1, k-1, target-nums[i], res)

217. 存在重复元素

题目描述

给定一个整数数组，判断是否存在重复元素。

如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

示例 1:

输入: [1,2,3,1]
输出: true

示例 2:

输入: [1,2,3,4]
输出: false

示例 3:

输入: [1,1,1,3,3,4,3,2,4,2]
输出: true

解题思路

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        
        
        if len(nums) <= 1:
            return False
        
        set1 = set(nums)
        return len(set1) != len(nums)

219. 存在重复元素 II

题目描述

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。

示例 1:

输入: nums = [1,2,3,1], k = 3
输出: true

示例 2:

输入: nums = [1,0,1,1], k = 1
输出: true

示例 3:

输入: nums = [1,2,3,1,2,3], k = 2
输出: false

解题思路

class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        
        if len(nums) <= 0 or k <= 0:
            return False
        
        Dict = {}
        for i in range(len(nums)):
            if nums[i] not in Dict:
                Dict[nums[i]] = i
            else:
                if i - Dict[nums[i]] <= k:
                    return True
                Dict[nums[i]] = i
        
        return False

228. 汇总区间

题目描述

给定一个无重复元素的有序整数数组，返回数组区间范围的汇总。

示例 1:

输入: [0,1,2,4,5,7]
输出: ["0->2","4->5","7"]
解释: 0,1,2 可组成一个连续的区间; 4,5 可组成一个连续的区间。

示例 2:

输入: [0,2,3,4,6,8,9]
输出: ["0","2->4","6","8->9"]
解释: 2,3,4 可组成一个连续的区间; 8,9 可组成一个连续的区间。

解题思路

class Solution(object):
    def summaryRanges(self, nums):
        """
        :type nums: List[int]
        :rtype: List[str]
        """

        if len(nums) == 0:
            return []
        
        res = []
        i = 0
        while i < len(nums):
            j = i
            while j < len(nums)-1 and nums[j+1] == nums[j]+1:
                j += 1
            if i == j:
                res.append(str(nums[i]))
            else:
                res.append(str(nums[i])+'->'+str(nums[j]))
            i = j+1
        
        return res

229. 求众数 II

题目描述

给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

示例 1:

输入: [3,2,3]
输出: [3]

示例 2:

输入: [1,1,1,3,3,2,2,2]
输出: [1,2]

解题思路

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        
        if len(nums) == 0:
            return []
        
        Dict = {}
        for x in nums:
            if x not in Dict:
                Dict[x] = 1
            else:
                Dict[x] += 1
        
        res = []
        for x in set(nums):
            if Dict[x] > len(nums)//3:
                res.append(x)
        
        return res

238. 除自身以外数组的乘积

题目描述

给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

输入: [1,2,3,4]
输出: [24,12,8,6]

说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

进阶：
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

解题思路

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        
        if len(nums) == 0:
            return []
        
        res = [1]*len(nums)
        
        for i in range(1, len(nums)):
            res[i] = res[i-1]*nums[i-1]
        
        temp = 1
        for i in range(len(nums)-2, -1, -1):
            temp *= nums[i+1]
            res[i] *= temp
        
        return res

268. 缺失数字

题目描述

给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

示例 1:

输入: [3,0,1]
输出: 2

示例 2:

输入: [9,6,4,2,3,5,7,0,1]
输出: 8

说明:
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

解题思路

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        
        res = len(nums)
        
        for i in range(len(nums)):
            res ^= nums[i]^i
        
        return res

283. 移动零

题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

• 必须在原数组上操作，不能拷贝额外的数组。
• 尽量减少操作次数。

解题思路

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        
        if len(nums) <= 1:
            return
        
        index = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[index] = nums[i]
                index += 1
        nums[index:] = [0] * (len(nums)-index)

287. 寻找重复数

题目描述

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

输入: [1,3,4,2,2]
输出: 2

示例 2:

输入: [3,1,3,4,2]
输出: 3

说明：

• 不能更改原数组（假设数组是只读的）。
• 只能使用额外的 O(1) 的空间。
• 时间复杂度小于 O(n2) 。
• 数组中只有一个重复的数字，但它可能不止重复出现一次。

解题思路

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) <= 1:
            return 0
        
        fast = nums[nums[0]]
        slow = nums[0]
        while fast != slow:
            fast = nums[nums[fast]]
            slow = nums[slow]
        
        fast = 0
        while fast != slow:
            fast = nums[fast]
            slow = nums[slow]
        
        return fast

289. 生命游戏

题目描述

根据百度百科，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在1970年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞具有一个初始状态 live（1）即为活细胞， 或 dead（0）即为死细胞。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

• 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
• 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
• 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
• 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；

根据当前状态，写一个函数来计算面板上细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。

示例:

输入: 
[
  [0,1,0],
  [0,0,1],
  [1,1,1],
  [0,0,0]
]
输出: 
[
  [0,0,0],
  [1,0,1],
  [0,1,1],
  [0,1,0]
]

进阶:

• 你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
• 本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题？

解题思路

class Solution(object):
    def gameOfLife(self, board):
        """
        :type board: List[List[int]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        
        
        if len(board) == 0:
            return
        Live = []
        Dead = []
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == 1:
                    if self.judgeLive(board, i, j):
                        Live.append((i,j))
                    else:
                        Dead.append((i,j))
                else:
                    if self.judgeDead(board, i, j):
                        Live.append((i,j))
                    else:
                        Dead.append((i,j))
        
        for pair in Live:
            board[pair[0]][pair[1]] = 1
        for pair in Dead:
            board[pair[0]][pair[1]] = 0
        
    def judgeLive(self, board, i, j):
        count = 0
        move = [[0,1], [0,-1], [1,0], [-1,0],[1,1],[1,-1],[-1,1],[-1,-1]]
        for pair in move:
            xnext = i+pair[0]
            ynext = j+pair[1]
            if 0<=xnext<len(board) and 0<=ynext<len(board[0]) and board[xnext][ynext] == 1:
                count += 1
        return True if 2<=count<=3 else False
    
    def judgeDead(self, board, i, j):
        count = 0
        move = [[0,1], [0,-1], [1,0], [-1,0],[1,1],[1,-1],[-1,1],[-1,-1]]
        for pair in move:
            xnext = i+pair[0]
            ynext = j+pair[1]
            if 0<=xnext<len(board) and 0<=ynext<len(board[0]) and board[xnext][ynext] == 1:
                count += 1
        return True if count==3 else False

380. 常数时间插入、删除和获取随机元素

题目描述

设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。

• insert(val)：当元素 val 不存在时，向集合中插入该项。
• remove(val)：元素 val 存在时，从集合中移除该项。
• getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

示例 :

// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();

// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);

// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);

// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);

// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();

// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomSet.remove(1);

// 2 已在集合中，所以返回 false 。
randomSet.insert(2);

// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
randomSet.getRandom();

解题思路

class RandomizedSet(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.keyIndex = {}#记录键、下标对
        self.indexKey = {}#记录下标、键对
        self.len = 0#记录长度，便于随机返回元素
        
    def insert(self, val):
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        #插入时，分别对两个哈希表都进行插入，同时len+1
        if val not in self.keyIndex:
            self.len += 1
            self.keyIndex[val] = self.len
            self.indexKey[self.len] = val
            return True
        return False
        
        

    def remove(self, val):
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        :type val: int
        :rtype: bool
        """
        #删除时将index_key中键为len的覆盖到键为key_index[val]，然后删除键为len的；key_index操作类似。最后len-1
        if val in self.keyIndex:
            self.indexKey[self.keyIndex[val]] = self.indexKey[self.len]
            self.keyIndex[self.indexKey[self.len]] = self.keyIndex[val]
            self.indexKey.pop(self.len)
            self.keyIndex.pop(val)
            self.len -= 1
            return True
        return False
        

    def getRandom(self):
        """
        Get a random element from the set.
        :rtype: int
        """
        return self.indexKey[random.randint(1, self.len)]


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

class RandomizedSet(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.set = []
        

    def insert(self, val):
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        if val not in self.set:
            self.set.append(val)
            return True
        else:
            return False
        

    def remove(self, val):
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        :type val: int
        :rtype: bool
        """
        if val in self.set:
            self.set.remove(val)
            return True
        else:
            return False
        
        
        

    def getRandom(self):
        """
        Get a random element from the set.
        :rtype: int
        """
        import random
        
        return self.set[random.randint(0, len(self.set)-1)]


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

381. O(1) 时间插入、删除和获取随机元素 - 允许重复

题目描述

设计一个支持在平均 时间复杂度 O(1) 下， 执行以下操作的数据结构。

注意: 允许出现重复元素。

• insert(val)：向集合中插入元素 val。
• remove(val)：当 val 存在时，从集合中移除一个 val。
• getRandom：从现有集合中随机获取一个元素。每个元素被返回的概率应该与其在集合中的数量呈线性相关。

示例:

// 初始化一个空的集合。
RandomizedCollection collection = new RandomizedCollection();

// 向集合中插入 1 。返回 true 表示集合不包含 1 。
collection.insert(1);

// 向集合中插入另一个 1 。返回 false 表示集合包含 1 。集合现在包含 [1,1] 。
collection.insert(1);

// 向集合中插入 2 ，返回 true 。集合现在包含 [1,1,2] 。
collection.insert(2);

// getRandom 应当有 2/3 的概率返回 1 ，1/3 的概率返回 2 。
collection.getRandom();

// 从集合中删除 1 ，返回 true 。集合现在包含 [1,2] 。
collection.remove(1);

// getRandom 应有相同概率返回 1 和 2 。
collection.getRandom();

解题思路

class RandomizedCollection(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = []
        

    def insert(self, val):
        """
        Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        if val not in self.data:
            self.data.append(val)
            return True
        else:
            self.data.append(val)
            return False
        

    def remove(self, val):
        """
        Removes a value from the collection. Returns true if the collection contained the specified element.
        :type val: int
        :rtype: bool
        """
        if val not in self.data:
            return False
        else:
            self.data.remove(val)
            return True
        

    def getRandom(self):
        """
        Get a random element from the collection.
        :rtype: int
        """
        return random.choice(self.data)


# Your RandomizedCollection object will be instantiated and called as such:
# obj = RandomizedCollection()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

414. 第三大的数

题目描述

给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。

示例 1:

输入: [3, 2, 1]

输出: 1

解释: 第三大的数是 1.

示例 2:

输入: [1, 2]

输出: 2

解释: 第三大的数不存在, 所以返回最大的数 2 .

示例 3:

输入: [2, 2, 3, 1]

输出: 1

解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。
存在两个值为2的数，它们都排第二。

解题思路

class Solution(object):
    def thirdMax(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        if len(nums) == 0:
            return 0
        
        if len(nums) <= 2:
            return max(nums)
        
        s1, s2, s3 = float('-inf'), float('-inf'), float('-inf')
        
        for num in nums:
            if num > s1:
                s1, s2, s3 = num, s1, s2
            elif num < s1 and num > s2:
                s2, s3 = num, s2
            elif num < s2 and num > s3:
                s3 = num
        
        return s3 if s3 != float('-inf') else max(s1, s2)

442. 数组中重复的数据

题目描述

给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。

找到所有出现两次的元素。

你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？

示例：

输入:
[4,3,2,7,8,2,3,1]

输出:
[2,3]

解题思路

class Solution(object):
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        
        if len(nums) <= 1:
            return []
        
        res = []
        
        for x in nums:
            if nums[abs(x)-1] < 0:
                res.append(abs(x))
            else:
                nums[abs(x)-1] *= -1
        
        return res

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

题目描述

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

找到所有在 [1, n] 范围之间没有出现在数组中的数字。

您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

示例:

输入:
[4,3,2,7,8,2,3,1]

输出:
[5,6]

解题思路

class Solution(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        
        
        if len(nums) == 0:
            return []
        
        for x in nums:
            if nums[abs(x)-1] > 0:
                nums[abs(x)-1] *= -1    
        
        res = []
        for i in range(len(nums)):
            if nums[i] > 0:
                res.append(i+1)
        
        return res