1.二分查找
704.二分查找
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
示例 1:
1 2 3
| 输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4
|
示例 2:
1 2 3
| 输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1
|
思路
这道题目的前提是数组为有序数组,同时题目还强调数组中无重复元素,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的,这些都是使用二分法的前提条件,当大家看到题目描述满足如上条件的时候,可要想一想是不是可以用二分法了。
二分查找涉及的很多的边界条件,逻辑比较简单,但就是写不好。例如到底是 while(left < right)
还是 while(left <= right)
,到底是right = middle
呢,还是要right = middle - 1
呢?
大家写二分法经常写乱,主要是因为对区间的定义没有想清楚,区间的定义就是不变量。要在二分查找的过程中,保持不变量,就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作,这就是循环不变量规则。
写二分法,区间的定义一般为两种,左闭右闭即[left, right],或者左闭右开即[left, right)。
下面我用这两种区间的定义分别讲解两种不同的二分写法。
二分法第一种写法
第一种写法,我们定义 target 是在一个在左闭右闭的区间里,也就是[left, right] (这个很重要非常重要)。
区间的定义这就决定了二分法的代码应该如何写,因为定义target在[left, right]区间,所以有如下两点:
- while (left <= right) 要使用 <= ,因为left == right是有意义的,所以使用 <=
- if (nums[middle] > target) right 要赋值为 middle - 1,因为当前这个nums[middle]一定不是target,那么接下来要查找的左区间结束下标位置就是 middle - 1
例如在数组:1,2,3,4,7,9,10中查找元素2,如图所示:
代码如下:(详细注释)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| class Solution { public: int search(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; while (left <= right) { int middle = left + ((right - left) / 2); if (nums[middle] > target) { right = middle - 1; } else if (nums[middle] < target) { left = middle + 1; } else { return middle; } } return -1; } };
|
1 2 3 4 5 6 7 8 9 10 11 12 13
| int search(int* nums, int numsSize, int target){ int pivot,left=0,right=numsSize-1; while (left <=right) { pivot = left + (right-left)/2; if(nums[pivot]==target) return pivot; if(nums[pivot]>target) right=pivot-1; else left=pivot+1; } return -1; }
|
二分法第二种写法
如果说定义 target 是在一个在左闭右开的区间里,也就是[left, right) ,那么二分法的边界处理方式则截然不同。
有如下两点:
- while (left < right),这里使用 < ,因为left == right在区间[left, right)是没有意义的
- if (nums[middle] > target) right 更新为 middle,因为当前nums[middle]不等于target,去左区间继续寻找,而寻找区间是左闭右开区间,所以right更新为middle,即:下一个查询区间不会去比较nums[middle]
在数组:1,2,3,4,7,9,10中查找元素2,如图所示:(注意和方法一的区别)
代码如下:(详细注释)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| class Solution { public: int search(vector<int>& nums, int target) { int left = 0; int right = nums.size(); while (left < right) { int middle = left + ((right - left) >> 1); if (nums[middle] > target) { right = middle; } else if (nums[middle] < target) { left = middle + 1; } else { return middle; } } return -1; } };
|
相关题目
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
示例 2:
示例 3:
示例 4:
暴力解法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| class Solution { public: int searchInsert(vector<int>& nums, int target) { for (int i = 0; i < nums.size(); i++) { if (nums[i] >= target) { return i; } } return nums.size(); } };
|
二分法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| class Solution { public: int searchInsert(vector<int>& nums, int target) { int left=0; int right=nums.size()-1; while(left<=right){ int middle = left + ((right-left)/2); if(nums[middle]<target) left=middle + 1; else if(nums[middle]>target) right=middle-1; else return middle; } return right+1; } };
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| class Solution { public: int searchInsert(vector<int>& nums, int target) { int n = nums.size(); int left = 0; int right = n; while (left < right) { int middle = left + ((right - left) >> 1); if (nums[middle] > target) { right = middle; } else if (nums[middle] < target) { left = middle + 1; } else { return middle; } } return right; } };
|
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
进阶:你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?
示例 1:
- 输入:nums = [5,7,7,8,8,10], target = 8
- 输出:[3,4]
示例 2:
- 输入:nums = [5,7,7,8,8,10], target = 6
- 输出:[-1,-1]
示例 3:
- 输入:nums = [], target = 0
- 输出:[-1,-1]
下面我来把所有情况都讨论一下。
寻找target在数组里的左右边界,有如下三种情况:
- 情况一:target 在数组范围的右边或者左边,例如数组{3, 4, 5},target为2或者数组{3, 4, 5},target为6,此时应该返回{-1, -1}
- 情况二:target 在数组范围中,且数组中不存在target,例如数组{3,6,7},target为5,此时应该返回{-1, -1}
- 情况三:target 在数组范围中,且数组中存在target,例如数组{3,6,7},target为6,此时应该返回{1, 1}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| / 二分查找,寻找target的右边界(不包括target)
int getRightBorder(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; int rightBorder = -2; while (left <= right) { int middle = left + ((right - left) / 2); if (nums[middle] > target) { right = middle - 1; } else { left = middle + 1; rightBorder = left; } } return rightBorder; }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
|
int getLeftBorder(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; int leftBorder = -2; while (left <= right) { int middle = left + ((right - left) / 2); if (nums[middle] >= target) { right = middle - 1; leftBorder = right; } else { left = middle + 1; } } return leftBorder; }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
| class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { int leftBorder = getLeftBorder(nums, target); int rightBorder = getRightBorder(nums, target); if (leftBorder == -2 || rightBorder == -2) return {-1, -1}; if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1}; return {-1, -1}; } private: int getRightBorder(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; int rightBorder = -2; while (left <= right) { int middle = left + ((right - left) / 2); if (nums[middle] > target) { right = middle - 1; } else { left = middle + 1; rightBorder = left; } } return rightBorder; } int getLeftBorder(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; int leftBorder = -2; while (left <= right) { int middle = left + ((right - left) / 2); if (nums[middle] >= target) { right = middle - 1; leftBorder = right; } else { left = middle + 1; } } return leftBorder; } };
|
2.移除元素
给你一个数组 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。
你不需要考虑数组中超出新长度后面的元素。
暴力解法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| class Solution { public: int removeElement(vector<int>& nums, int val) { int size=nums.size(); for(int i=0;i<size;i++){ if(nums[i]==val){ for (int j = i + 1; j < size; j++) { nums[j - 1] = nums[j]; } i--; size--; } } return size; } };
|
- 时间复杂度:$O(n^2)$
- 空间复杂度:$O(1)$
双指针法
双指针法(快慢指针法): 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
删除过程如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
|
class Solution { public: int removeElement(vector<int>& nums, int val) { int slowIndex = 0; for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) { if (val != nums[fastIndex]) { nums[slowIndex++] = nums[fastIndex]; } } return slowIndex; } };
|
3.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。
示例:
输入:s = 7, nums = [2,3,1,2,4,3] 输出:2 解释:子数组 [4,3] 是该条件下的长度最小的子数组。
暴力解法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| class Solution { public: int minSubArrayLen(int s, vector<int>& nums) { int result = INT32_MAX; int sum = 0; int subLength = 0; for (int i = 0; i < nums.size(); i++) { sum = 0; for (int j = i; j < nums.size(); j++) { sum += nums[j]; if (sum >= s) { subLength = j - i + 1; result = result < subLength ? result : subLength; break; } } } return result == INT32_MAX ? 0 : result; } };
|
滑动窗口
接下来就开始介绍数组操作中另一个重要的方法:滑动窗口。
所谓滑动窗口,就是不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果。
这里还是以题目中的示例来举例,s=7, 数组是 2,3,1,2,4,3,来看一下查找的过程:
最后找到 4,3 是最短距离。
其实从动画中可以发现滑动窗口也可以理解为双指针法的一种!只不过这种解法更像是一个窗口的移动,所以叫做滑动窗口更适合一些。
在本题中实现滑动窗口,主要确定如下三点:
- 窗口内是什么?
- 如何移动窗口的起始位置?
- 如何移动窗口的结束位置?
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
窗口的起始位置如何移动:如果当前窗口的值大于s了,窗口就要向前移动了(也就是该缩小了)。
窗口的结束位置如何移动:窗口的结束位置就是遍历数组的指针,窗口的起始位置设置为数组的起始位置就可以了。
解题的关键在于 窗口的起始位置如何移动,如图所示:
可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况,不断调节子序列的起始位置。从而将$O(n^2)$的暴力解法降为$O(n)$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| class Solution { public: int minSubArrayLen(int s, vector<int>& nums) { int result = INT32_MAX; int sum = 0; int i = 0; int subLength = 0; for (int j = 0; j < nums.size(); j++) { sum += nums[j]; while (sum >= s) { subLength = (j - i + 1); result = result < subLength ? result : subLength; sum -= nums[i++]; } } return result == INT32_MAX ? 0 : result; } };
|
时间复杂度:$O(n)$
空间复杂度:$O(1)$
4.螺旋矩阵
给你一个正整数 n
,生成一个包含 1
到 n2
所有元素,且元素按顺时针顺序螺旋排列的 n x n
正方形矩阵 matrix
。
示例 1:
1 2
| 输入:n = 3 输出:[[1,2,3],[8,9,4],[7,6,5]]
|
示例 2:
这道题目可以说在面试中出现频率较高的题目,本题并不涉及到什么算法,就是模拟过程,但却十分考察对代码的掌控能力。
要如何画出这个螺旋排列的正方形矩阵呢?
相信很多同学刚开始做这种题目的时候,上来就是一波判断猛如虎。
结果运行的时候各种问题,然后开始各种修修补补,最后发现改了这里哪里有问题,改了那里这里又跑不起来了。
大家还记得我们在这篇文章数组:每次遇到二分法,都是一看就会,一写就废 (opens new window)中讲解了二分法,提到如果要写出正确的二分法一定要坚持循环不变量原则。
而求解本题依然是要坚持循环不变量原则。
模拟顺时针画矩阵的过程:
- 填充上行从左到右
- 填充右列从上到下
- 填充下行从右到左
- 填充左列从下到上
由外向内一圈一圈这么画下去。
可以发现这里的边界条件非常多,在一个循环中,如此多的边界条件,如果不按照固定规则来遍历,那就是一进循环深似海,从此offer是路人。
这里一圈下来,我们要画每四条边,这四条边怎么画,每画一条边都要坚持一致的左闭右开,或者左开又闭的原则,这样这一圈才能按照统一的规则画下来。
那么我按照左闭右开的原则,来画一圈,大家看一下:
这里每一种颜色,代表一条边,我们遍历的长度,可以看出每一个拐角处的处理规则,拐角处让给新的一条边来继续画。
这也是坚持了每条边左闭右开的原则。
一些同学做这道题目之所以一直写不好,代码越写越乱。
就是因为在画每一条边的时候,一会左开又闭,一会左闭右闭,一会又来左闭右开,岂能不乱。
代码如下,已经详细注释了每一步的目的,可以看出while循环里判断的情况是很多的,代码里处理的原则也是统一的左闭右开。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
| class Solution { public: vector<vector<int>> generateMatrix(int n) { vector<vector<int>> res(n, vector<int>(n, 0)); int startx = 0, starty = 0; int loop = n / 2; int mid = n / 2; int count = 1; int offset = 1; int i,j; while (loop --) { i = startx; j = starty;
for (j = starty; j < starty + n - offset; j++) { res[startx][j] = count++; } for (i = startx; i < startx + n - offset; i++) { res[i][j] = count++; } for (; j > starty; j--) { res[i][j] = count++; } for (; i > startx; i--) { res[i][j] = count++; }
startx++; starty++;
offset += 2; }
if (n % 2) { res[mid][mid] = count; } return res; } };
|