数组Tag部分

这部分主要用来记录总结Leetcode中数组部分的题目和思路分析

语言：python

NO.1 Two Sums

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly\ one solution, and you may not use the same element twice.

Example:
1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

思路

首先想到的主要是两个循环，即首先挑选一个nums中的数nums[i]，然后在剩下的数里面寻找是否有符合 target - nums[i] 的数字【brute force】。但两个循环下，算法复杂度为 $O(n^2)$ 。于是我们想到了用Hash table把数据存起来，然后再对合适的key进行访问。这里所谓的合适的key就是target - nums[i] 的值。于是我们可以选择先把nums中的数字循环存储起来，然后再访问key为target - nums[i]【two-pass hash table】,或者我们可以进行一次pass在存储的过程中寻找指定的key【one-pass hash table】.

在使用python的时候判断 if A in dict, 判断的是A是否在dict的key中，若想要判断A是否是其中的一个value，那么我们需要用 if A in dict.values(),然后通过 .index(value) 函数来找到对应的键值
在使用python的时候可以直接用dict，方便查找，但是在使用其他语言的时候需要用到hash map

solution

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

NO.4 Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

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

The median is 2.0
Example 2:
1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

思路

首先想到的就是：那我可以把两个数列按顺序排列在一起，然后找到中值(X)，这样的话算法复杂度是 $O(m+n)$【brute force】

现在已知的信息是：1. 中值必定是两个数列按序放在一起之后第 (m+n)/2 个；2. 两个数列都是有序排列的；3. 如果要求算法复杂度是 $O(log(m+n))$，那么可能有二分法的类似方法。

（那么怎么做呢）

这样想一下，中值就是处在一个已排列的数列中间的数，如果是奇数，那么第 $\frac{n+1}{2}$ 个位置就是中位数，如果是偶数，那么中位数为 $\frac{n}{2}$ 和 $\frac{n}{2}+1$ 个数的平均值。所以说我们想要做的就是在数列 nums1 和数列nums2中分别找到不同的partition，将两个数列分别分成两个部分，若两个数组左侧的部分的合集恰好都小于右侧部分的合集，那么这两个partition都是正确的，然后我们再根据两个数列中的总个数来计算中位数。

所以现在首要的问题就是考虑如何将两个partition分割正确。

因为两个数列中的数总个数是不变，因此如果对于nums1和nums2来说，两个数列分割后左侧数字的总和是一个定值，我们计算这个定值为 $\frac{m+n+1}{2}$.
- 若 $m+n$ 是偶数，则 $max(nums1right[max], num2right[max])$ 就为合并后数列的中位数
- 若 $m+n$ 是奇数，则 $\frac{max(nums1left[max], num2left[max])+min(nums1right[min], num2right[min])}{2}$ 就为合并后数列的中位数。
  
  【这里也就是在讲，当把nums1 和nums2 分别分成两部分的时候，若总数为奇数，那么中位数是左侧两部分的最大值，若总数为偶数，那么中位数是右侧两部分的最小值和左侧两部分最大值的平均数。】

接下来就是要确定如何找到正确的针对于nums1 和nums2 的partition的位置。

1) 因为我们想要在比较短的数列中找partition，然后根据上面的定值 $\frac{m+n+1}{2}$ 得到比较长数列中的partition，所以我们定义较短的数列为 nums1, 另一个为 nums2.

m = len(nums1)
n = len(nums2)

if n < m:
  nums1, nums2, m, n = nums2, nums1, n, m

2) 接下来我们在nums1上进行初始partition定位，然后通过 $\frac{m+n+1}{2}$ 找到nums2 上的partition的定位。

1 2	i = (start + end)/2 j = (m + n + 1)/2 - i

3) 再开始判定之前，需要先确保输入的数组都不是空集，则，如果 $i == 0$ 那么我们可以得知 nums1 的左侧将是一个空集，nums1左侧的空集表明它总符合条件，相当于在集合中放置了一个 $-\infin $ .所以我们定义，若 partition的位置在最开头或者最末尾，会分别造成左侧的最大值为 $-\infin $ 右侧的最小值为 $+\infin $

if i == 0:
maxleft1 = -float('inf')
else:
maxleft1 = nums1[i-1]

if i == m:
minright1 = float('inf')             
else:
minright1 = nums1[i]

if j == 0:
maxleft2 = -float('inf')
else:
maxleft2 = nums2[j-1]

if j == n:
minright2 = float('inf')          
else:
minright2 = nums2[j]

4) 结束了边界情况的定义之后，我们来讨论一下何时需要移动这些partition。

最佳情况是 maxleft1 <= minright2 && maxleft2 <= minright1, 如果这个成立，我们就可以根据总数的奇偶个数来判断中位数了

if (maxleft1 <= minright2) and (maxleft2 <= minright1):
  if (m + n) % 2 == 0:
  return (max(maxleft1, maxleft2) + min(minright1 , minright2)) / 2.0
  else:
  return max(maxleft1, maxleft2)

如果maxleft1 > minright2, 那么我们就说明数组一左侧的最大值大于数组二右侧的最小值，我们应该将数组一的partition向左移动，相应的数组二的partition向右移动。于是这里我们更新 end 的值。
1
2
elif (maxleft1 > minright2):
end = i - 1
反之，我们把数组一的partition向右移动
1
2
else:
start = i + 1

然后我们就一直重复这个步骤直到找到正确的中位数。

在python中，表示正负无穷的时候需要用 float(‘inf’)

Solution

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        m = len(nums1)
        n = len(nums2)
        
        if n < m:
            nums1, nums2, m, n = nums2, nums1, n, m
            
        start = 0
        end = m 
        while start <= end:
            
            i = (start + end)/2
            j = (m + n + 1)/2 - i
            
            
            if i == 0:
                maxleft1 = -float('inf')
            else:
                maxleft1 = nums1[i-1]

            if i == m:
                minright1 = float('inf')             
            else:
                minright1 = nums1[i]
            
            if j == 0:
                maxleft2 = -float('inf')
            else:
                maxleft2 = nums2[j-1]
                
            if j == n:
                minright2 = float('inf')          
            else:
                minright2 = nums2[j]


            if (maxleft1 <= minright2) and (maxleft2 <= minright1):

                if (m + n) % 2 == 0:
                    return (max(maxleft1, maxleft2) + min(minright1 , minright2)) / 2.0
                else:
                    return max(maxleft1, maxleft2)

            elif (maxleft1 > minright2):
                end = i - 1
            else:
                start = i + 1

NO.11 Container with most water

思路

首先想到的就是把所有可能的container的area都求一遍【brute force】。这样的话就造成了两个循环，时间复杂度为 $O(n^2)$. 但如果有一种方法能让两边的边界都动起来，那可能会更容易一些。

那我们来想一下，一个水桶的容量大小由什么决定，是由两个边之间的距离以及两条边之中的最短边决定。所以说在一开始，我们不断的改变最短边，祈求下一个边界是一个长一些的边界。

Solution

def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        i = 0
        j = len(height) - 1
        
        area = 0
        while i < j:
            left_bound = height[i]
            right_bound = height[j]
            width = j - i
            if width * min(left_bound, right_bound) > area:
                area = width * min(left_bound, right_bound)
                
            if left_bound < right_bound:
                i = i + 1
            else:
                j = j - 1
        return area

NO.15 3 Sums

思路

以数组中的某个数为标准去找另外两个数的和，使得三个数加在一起的总和为0.

NO. 33 Search in Rotated Array

题目

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:
1
2
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

解题思路

【午夜梦回，我拍着胸口问我自己，为啥别人的二分法就正好找到，而我的就总是Time Limit Exceeded。是我的上下界出了什么问题吗。是的。】

这道题和传统的二分法查找类似，有一个不同的点就是这里是转了圈了循环数列。针对于循环数列，不同的点就在于不能按照平常的根据中值来判断target的位置。我们首先需要判断的是pivot的位置，也就是从哪里开始循环的。正常情况下，如果一个数列是顺序排列，那么它左边端点的值会小于右边端点的值，这里有两个判断：

if nums[left] > nums[mid]: 这里说明的是nums数列的最左值大于nums中间值，表明pivot在左半边
if nums[mid] > nums[right]: 表明pivot在右半边

但值得注意的是，朋友们，这两种不是全部的情况，因为有可能你分着分着，你寻找的数列就变成一个正常顺序的数列了，对于正常的数列来说，上面两个调节都不成立，于是你将会陷入无限的while循环。

所以在选择上面的一个条件，之后用else，表明pivot在另一边，或者数列已经回归正常排序了

对于二分法来说，有两个部分是重要的（我觉得）。一个是要考虑什么时候找到了target，一个是要考虑什么时候更换边界。在更换边界的时候不需要考虑在更换边界过后怎么去找target，只需要更换边界值就行了。

还有一个是在更换边界的时候不要直接用mid的值去更换left或者right，要进行 + 1和 -1的处理，不然也会造成无限while循环。因为当left和right是相连的时候，mid和right相等，就会造成不断更新right，但其实没动。

Solution

def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """    
        left = 0
        right = len(nums) - 1
        while left <= right:
            
            mid = (left +  right)/2
            # When find the value
            if nums[left] == target: return left
            if nums[right] == target: return right
            if nums[mid] == target: return mid
            
            # Updating end point.
            if nums[left] > nums[mid]:
                # pivot on the left, right part sorted
                if target > nums[mid] and target < nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1                   
            else:
                # pivot on the right, left part sorted
                if target > nums[left] and target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
                    
        return -1

NO.153&154 Find Minimum in Rotated Sorted Array

既然说到了循环数列，就不得不提一下相似的题。

题目

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1:
1
2
Input: [3,4,5,1,2] 
Output: 1

解题思路

这个题和上面一样，也用二分法来，同样也要注意的两个点是：什么时候停下来得到return的值，什么时候更新边界点。

之前一道题因为有给定的target，所以只需要判定basis case是不是等于target就可以了。这道题在问找到最小值，那什么时候返回最小值呢。rotate的数列有个特点就是左边端点的值大于右边端点的值，一旦我们得知左边端点的值小于右边端点的值，那么pivot一定在另一侧。pivot还有一个特点就是小于等于右边的值，同时小于等于左侧的值。但是这个只能用在长度大于三的数列中，所以放弃这个条件。

这个帖子说的特别好奥：https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/discuss/167981/Beats-100-Binary-Search-with-Explanations 看的很明白

说白了，找最小值就是找最小的值，我们在做比较，更换端点index的时候其实就可以得出这些结论。假设我们的左边端点用left表示，右边端点用right表示，中间点用mid表示，那么，有以下几种情况：

nums[Left] <= nums[mid] <= nums[right], 这种是标准的，完全没有rotate的部分，在这种情况下，为了找到最小值，我们更新寻找数列的右端点right = right -1 逐渐往里缩就可以。
nums[Left] <= nums[mid] > nums[right], 这种情况下左半边的部分是排序好的，右半边是不好的，所以我们要把左侧端点缩至 mid +1, 因为这里mid比right大，所以我们可以舍弃mid这一点上的值。
nums[Left] >= nums[mid] < nums[right], 这种情况下，右半边部分是排序好的，左半边是不好的，所以我们要focus在左侧，又因为nums[Left] >= nums[mid]，所以right只能缩到mid这个值，不能为mid-1，因为mid可能是最小值，但Left可以缩为Left + 1
nums[Left]>nums[mid]>nums[right],这种情况不符合题目要求。

Solution

def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        left = 0
        right = len(nums) - 1
        
        while left <= right:
            mid = (left +  right)/2
            
            if nums[left] > nums[mid]:
                left = left + 1
                right = mid
            elif nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = right - 1
                
        return nums[left]

NO.34 Find First and Last Position of Element in Sorted Array

题目

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

1 2	Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]

解题思路

这就麻烦了，让找两个点，但是又要用binary search，怎么搞呢。我们就分开找这个起始点和终止点。这个leetcode帖子)写的比较完善。

我们先找target value的起始点，如果找不到的话，叮，结束，返回 [-1, -1]

怎么找呢.找点的话还是要设置左边界，设置右边界，然后不断的更新，有点像单纯的binary search：
- 如果 nums[mid] > target, 那么所求点在mid右侧，更新 right = mid - 1
- 如果nums[mid] < target, 那么所求点在mid左侧，更新 left = mid + 1
- 如果nums[mid] == target, 那么所求点要么是mid这点，要么在mid的左侧，更新 right = mid
然后再寻找target value的终止点。和上面一样
- 如果 nums[mid] > target, 那么所求点在mid右侧，更新 right = mid - 1
- 如果nums[mid] < target, 那么所求点在mid左侧，更新 left = mid + 1
- 如果nums[mid] == target, 那么所求点要么是mid这点，要么在mid的右侧，更新 left = mid

然后更新这两个点就可以。

注意这里在更新左右临界点的时候有个trick，如果是 mid = (left + right)/2 那么在更新left的的时候就不能单纯的left = mid，这样当只有两个数的时候就会陷入无限循环，因为left = (left + right)/2，所以在过程中若是存在left = mid的更新步骤，需要将mid定义为 mid = (left + right)/2 +1。同样的，若是在过程总存在right = mid的更新步骤，直接用 mid = (left + right)/2 即可。

Solution

def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        
        if not nums:
            return [-1, -1]
        def findstart(nums, target):
            left = 0
            right = len(nums) - 1
        
            while left < right:
                mid = (left + right) / 2

                if nums[mid] >= target:
                    right = mid                 
                elif nums[mid] < target:
                    left = mid + 1
            return left
        
        
        def findend(nums, target):
        
            left = 0
            right = len(nums) - 1

            while left < right:
                mid = (left + right)/2 + 1

                if nums[mid] > target:
                    right = mid - 1
                elif nums[mid] <= target:
                    left = mid 
                                
            return left
    
        start = findstart(nums, target)
        print(start)
        end = findend(nums, target)
        print(end)
        if nums[start] == target:
            return [start, end]
        else:
            return [-1, -1]

NO. 35 Search insert position

题目

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:
1
2
Input: [1,3,5,6], 5
Output: 2
Example 2:
1
2
Input: [1,3,5,6], 2
Output: 1

解题思路

给定的是sorted的数列，那么在找插入点的时候该点前面的值肯定都比target要小，所以就要找到第一个比target大的数，那个点就是我们要找的点，如果遍历整个数列都没有比target大的值，那就说明target最大，返回nums的长度+1【Brute force】

可以用二分法吗？当然可以辽，就还是要分清，什么时候停止，什么时候更新边界。若要找到插入的位置，那么就说明该位置是刚刚大于或等于target的，所以我们可以缩小边界，来找到target的插入点。因为数列是有序排列的，所以该点右侧的数字都会大于或等于target，所以我们停止的条件就是

if nums[left] >= target: return left

然后看一下更新的条件，同样是对mid的值进行判断：

if nums[mid] == target: left = mid 【这里其实可以直接返回mid的值，但是为了保持逻辑的连贯性，我们把左index赋值为mid，这样再经过一次循环就可以return left 了】
if nums[mid] > target: right = mid【中值比target要大，所以target在mid左侧，更新right。因为我们要找的也是大于等于target的值，所以mid这一点不能错过，于是我们更新： right = mid】
if nums[mid] < target: left = mid + 1【中值比target要小，所以target在mid右侧，更新left。因为我们要找的是大于等于target的值，所以此处的mid可以跳过，更新left = mid + 1】
check一下 left更新的时候有mid + 1，所以这里mid取（left+right）/2不会造成持续的循环。

有一个特殊情况存在，就是我遍历了所有的值都没有得到想要得到的点，此时说明数列中所有的值都比target要小，所以直接返回数列长度。

Solution

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

光

算法 | 【Leetcode】数组array类题目总结

数组Tag部分

NO.1 Two Sums

思路

solution

NO.4 Median of Two Sorted Arrays

思路

Solution

NO.11 Container with most water

思路

Solution

NO.15 3 Sums

思路

NO. 33 Search in Rotated Array

题目

解题思路

Solution

NO.153&154 Find Minimum in Rotated Sorted Array

题目

解题思路

Solution

NO.34 Find First and Last Position of Element in Sorted Array

题目

解题思路

Solution

NO. 35 Search insert position

题目

解题思路

Solution