type
status
date
slug
summary
tags
category
icon
password
学习小结：
- 二维坐标转为一维坐标详解见例题三
- if语句是否有=的问题见例题二
- 重复元素问题见例题四
例题一：
- ‣
题目描述：
给定两个大小分别为
m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为
O(log (m+n))题解：
问题and重点
这个题目重点在于是不是可以想到怎么使用二分法，他也给提示了，时间复杂度是O(m+n)，所以我们要考虑怎么构造这个左右端点才可以符合条件，刚开始我也没有想到是这样的做法，借鉴了一下ai，确实强
这个题目思路是：
首先，我们要知道，我们mid的值不能超过数组的长度，所以我们的右端点应该取较短的哪一个值
然后下面就是具体实现，以及确定边界，mid的值应该分成mid1，mid2，因为有两个数组，这里我们确定一个分割点，对于第二个数组的分割点我们直接用（m+n）//2-mid1,这样可以保证两边的范围大小是一样的，可以保证中位数的条件
接下来就是保证边界问题，如果到达了边界就要开始赋值了，我们要保证两个数组的左边界分别小于两个数组的右边界，这样就可以保证单调性了
例题二：
题目描述
给你一个按照非递减顺序排列的整数数组
nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值
target，返回 [-1, -1]。你必须设计并实现时间复杂度为
O(log n) 的算法解决此问题题解：
问题and重点
这个题目考点就是在二分查找时的if语句判断的是否加上=
拿第一个函数举例
就像是第一个，nums[mid]<target 所以如果有重复的情况，就像是
第一次到了第二个8，但是这时候满足了第二个条件，此时指针还会往左走，直到l指向第一个8
例题三：
题目描述：
给你一个满足下述两条属性的
m x n 整数矩阵：- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数
target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。示例 1：
题解：
问题and重点：
这个题的重点是如何将二维坐标转换为一维坐标，这个是本题最大的收获点
例题四：
- ‣
题目描述：
已知存在一个按非降序排列的整数数组
nums ，数组中的值不必互不相同。在传递给函数之前，
nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。题解：
关键问题：
此题的关键有两个：
一个是旋转数组的左右区分问题
一个是去重问题：
如果一个数nums[l]与nums[mid]与nums[r]都是一个值，就会导致指针不知道王座还是往右走
例题五：
题目描述：
已知一个长度为
的数组，预先按照升序排列，经由
到
次
旋转
后，得到输入数组。例如，原数组
在变化后可能得到：
- 若旋转
4次，则可以得到[4,5,6,7,0,1,4]
- 若旋转
7次，则可以得到[0,1,4,4,5,6,7]
注意，数组
[a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。给你一个可能存在 重复 元素值的数组
nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。你必须尽可能减少整个过程的操作步骤。
示例 1：
示例 2：
题解：
关键重点：
此题的关键就是找到规律可以找到左右边界，能够区分左右区间，还有就是可以找到去除重复元素的方法
- Author:xiaowaaa
- URL:https://www.xiaowaaa.asia//article/1235df8d-8884-8086-bdfc-f71eed8a45b6
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!