【LeetCode练习|算法通关手册：Python版】03. 数组篇_随笔

【LeetCode练习|算法通关手册：Python版】03. 数组篇

2021.11.23-2021.11.25
Datawhale 11月学习内容；学习地址：https://algo.itcharge.cn/

文章目录

1. 二分查找
2. 二分下标题目
- LeetCode 704. 二分查找
- LeetCode 374. 猜数字大小
- LeetCode 35. 搜索插入位置
- LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置
- LeetCode 167. 两数之和 II - 输入有序数组
- LeetCode 153. 寻找旋转排序数组中的最小值
- Leetcode 154. 寻找旋转排序数组中的最小值 II
- LeetCode 33. 搜索旋转排序数组

1. 二分查找

基本算法思想：是一种在有序数组中查找某一特定元素的搜索算法。先确定待查找元素所在的区间范围，在逐步缩小范围，直到找到元素或找不到该元素为止。

每次查找时从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；
如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
如果在某一步骤数组为空，则代表找不到。

事例：假设原始序列为array=[3, 12, 24, 31, 46, 48, 52, 66, 69, 79, 82]，目标元素target=52。

开始时，low=0，high=10，mid=(low + high) / 2 = 5。
此时，比目标值小，说明在右侧。low=5+1=6，high=10，mid=(low + high) / 2 = 8。
此时，比目标值大，说明在左侧 low=6，high=mid-1=7，mid=(low + high) / 2 = 6。
就找到了
找不到就是，整个数数组找完了（条件：low > high）都没找到，那说明没有。

代码：

def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        # 在区间 [left, right] 内查找 target
        while left <= right:
            # 取区间中间节点
            mid = (left + right) // 2
            # 如果找到目标值，则直接返回中心位置
            if nums[mid] == target:
                return mid
            # 如果 nums[mid] 小于目标值，则在 [mid + 1, right] 中继续搜索
            elif nums[mid] < target:
                left = mid + 1
            # 如果 nums[mid] 大于目标值，则在 [left, mid - 1] 中继续搜索
            else:
                right = mid - 1
        # 未搜索到元素，返回 -1
        return -1

方法二：排除法思想

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        # 在区间 [left, right] 内查找 target
        while left < right:
            # 取区间中间节点
            mid = left + (right - left + 1) // 2
            # nums[mid] 大于目标值，排除掉不可能区间 [mid, right]，在 [left, mid - 1] 中继续搜索
            if nums[mid] > target:
                right = mid - 1 
            # nums[mid] 小于等于目标值，目标元素可能在 [mid, right] 中，在 [mid, right] 中继续搜索
            else:
                left = mid
        # 判断区间剩余元素是否为目标元素，不是则返回 -1
        return left if nums[left] == target else -1

if nums[mid] > target:如果中间值大于目标值，那么一定在左半部分
另一种情况就是不大于目标值，所以left = mid
最终left=right结束(和while条件相反的临界值)
return left if nums[left] == target 就是相等的话返回坐标，其他情况返回-1

2. 二分下标题目 LeetCode 704. 二分查找

https://leetcode-cn.com/problems/binary-search/

思路没有一点变化，和原理无异

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

LeetCode 374. 猜数字大小

https://leetcode-cn.com/problems/guess-number-higher-or-lower/

这道题多少感觉有点问题，以下是答案，如果有看懂的给我讲一下
int guess(int num) 来获取猜测结果

class Solution:
    def guessNumber(self, n: int) -> int:
        left = 1
        right = n
        while left <= right:
            mid = (right + left) // 2
            ans = guess(mid)
            if ans == 1:
                left = mid + 1
            elif ans == -1:
                right = mid - 1
            else:
                return mid
        return 0

LeetCode 35. 搜索插入位置

https://leetcode-cn.com/problems/search-insert-position/

为了效率满足，用了二叉查找，思路没有一点变化，和原理无异
唯一不同就是这里要输出插入位置
当找到一样值的时候，这个值得位置就是插入的位置
如果搜索到最后没找到这个值，也就是结束条件left > right,一定是应该插入到left这个位置，所以return left

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

        return left

LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置

https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

这道题如果按正常思路，从小到大找呗，然后找到输出就行。但是本题要求$O(logn)$

思想：

用二叉查找发先找到这个值
然后向两边找，直到出现不同

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:

        left = 0
        right = len(nums) - 1
        ans = [-1, -1]
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                nums.append(0.1)
                ans[0] = ans[1] = mid
                while (ans[0]-1>=0) and (nums[ans[0]-1] == target) :
                    ans[0] -= 1

                while (nums[ans[1]] == target) and ((ans[1]+1) <= len(nums)-1):
                    ans[1] += 1
                ans[1]= ans[1] -1

                return ans
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return ans

是在二分法相等的条件下做往两端延伸看是否与target相等。我遇到的问题就是边界的判断
当最左端是目标时，如【2,2,3】target =2，因为nums[-1]是有值的（list最后一个），但我们要防止它套圈,所以加了条件ans[0]-1 >= 0
另一个是最右端处理，因为+1 要超出nums长度的，所以我在末尾加了一个不可能出现的数nums.append(0.1),使得循环不超界
最后，我们尝试一下特殊的数组，比如【】，【1】，【2,2】是否满足

参考答案：

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        ans = [-1, -1]
        n = len(nums)
        # 空的情况
        if n == 0:
            return ans

        left = 0
        right = n - 1
		
		#排除法，最终是要搜索完，那么只有两种情况：没有目标值，和目标值最左端 
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            # 它这个即使现在找到目标值了，但是没有搜索完 还是会去逼近目标值最左端
            else:
                right = mid

       # 没有目标值，返回ans
        if nums[left] != target:
            return ans

        # 存在目标值，那么结束一定是在最左端
		ans[0] = left

        left = 0
        right = n - 1
		#同样的方法找最右端 
        while left < right:
            mid = left + (right - left + 1) // 2
            if nums[mid] > target:
                right = mid - 1
            else:
                left = mid

        if nums[left] == target:
            ans[1] = left

        return ans

这个算法的精彩在于while循环的排除法，它不是找到结束，而是查完表才结束
if nums[mid] < target:的else是nums[mid] >= target,然后让mid成为右端,也就是如果有目标值，那么左端一定存在目标值（右端也可能有）
循环完while,最后指针left,right指向同一个地方，只会出现两种情况：① 这个值不是目标值和② 这个值是目标值，且一定是目标值的最左端
同理第二个while找连续目标值的最右端

LeetCode 167. 两数之和 II - 输入有序数组

https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
条件：

有且只有一个有效答案
非递减顺序

想法1：

双层循环肯定是可以，但效率应该是最低的;

想法2：

一层循环+一层二分是可以实现的，效率稍微高一点
我采用第一层是i从小到大的循环，第二层是从left = i+1开始的二分查找

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:

        for i in range(len(numbers)):
            #从i+1开始找起
            left = i+1
            right = len(numbers) - 1
           
           #我们查找的目标值是num
			num = target - numbers[i]
            while left <= right:
                # 取区间中间节点
                mid = (left + right) // 2
                # 如果找到目标值，则直接返回中心位置
                if numbers[mid] == num:
                    return [i+1, mid+1]
                # 如果 nums[mid] 小于目标值，则在 [mid + 1, right] 中继续搜索
                elif numbers[mid] < num:
                    left = mid + 1
                # 如果 nums[mid] 大于目标值，则在 [left, mid - 1] 中继续搜索
                else:
                    right = mid - 1

LeetCode 153. 寻找旋转排序数组中的最小值

https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/

思想1：

常规思路遍历，找到最小值，输出，但效率低

思想2：

nums[mid] > nums[right]，最小值一定在mid右边
nums[mid]<=nums[right]，最小值一定在mid 或者mid左边

解析一下：

条件是非递减序列，按理说右边至少要和mid相等或者大的，但现在小了，那么一定是从头开始计算了，也就是起始值在mid右侧

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

循环结束条件 right = left ,若依return nums[right]也行

Leetcode 154. 寻找旋转排序数组中的最小值 II

https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

条件：

与上题不同之处，给你一个可能存在重复元素值的数组 nums
导致我们比右边大小时候，可能无法判断最小值的位置

【3,3,1,3】mid = 1,和右侧比我们无法判断位置

思想：

如果 nums[mid] > nums[right]，则最小值不可能在 mid 左侧，一定在 mid 右侧
如果 nums[mid] < nums[right]，则最小值一定在 mid 左侧，
当 nums[mid] == nums[right]，无法判断在mid 的哪一侧，可以采用 right = right - 1 逐步缩小区域。

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

LeetCode 33. 搜索旋转排序数组

https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

条件：

互不相同
升序排列

想法：

思想就是看mid两边哪边是连续的，再判断target是否在连续这端取值，如果是，那再进行二分

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

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

示例 3：
输入：nums = [1], target = 0
输出：-1

mid = (0 + 6) // 2 == 3, 此时nums[mid] == 7，下面开始判断。

如果 nums[left] == nums[mid]:，返回mid
如果 nums[left] <= nums[mid]: 左侧是连续增大的，没有断层

① 当nums[left] <= target < nums[mid]，那么如果有答案，就在这之间right = mid - 1

②如果不是上一种情况那么又在mid右侧，缩减left = mid + 1
如果nums[left] > nums[mid]，那么右侧是连续的

① nums[mid] < target <= nums[right],此时我们缩减left += 1

②否则，缩减right = mid - 1

class Solution:
    def search(self, nums, target):
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1

难点：

while left <= right为什么要有=号?

因为我们相等的时候还需要判断，这个mid的情况，也就是存在不一定的存在的情况，所以要判断完才能结束。
elif nums[left] <= nums[mid]:为什么要有=号?

边界问题，我们重点看的是哪些地方连续。

如果条件是：nums[left] < nums[mid],比如【3,1】，target =1 那么我们mid =0 我们认为左边不连续，是右边连续，右边是个1<3，(连续的话一定是nums[right] >= nums[mid]) 所以它认为找不到，输出了-1,就错过了正确答案。

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5593337.html

【LeetCode练习|算法通关手册：Python版】03. 数组篇

发表评论

评论列表（0条）