二分查找
力扣题目 704. 二分查找
给定一个 n
个元素有序的(升序)整型数组 nums
和一个目标值 target
,写一个函数搜索 nums
中的 target
,如果目标值存在返回下标,否则返回 -1
。
示例1:
输入:
nums = [-1,0,3,5,9,12], target = 9
输出:4
解释:9 出现在 nums 中并且下标为 4
示例2:
输入:
nums = [-1,0,3,5,9,12], target = 2
输出:-1
解释:2 不存在 nums 中因此返回 -1
提示:
- 你可以假设
nums
中的所有元素是不重复的。 n
将在[1, 10000]
之间。nums
的每个元素都将在[-9999, 9999]
之间。
思路
题目前提是数组为有序数组,题目还强调数组中无重复元素。因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的。
二分法第一种写法
target 是在左闭右闭的区间里查找,即[left,right]
。
- 循环条件:
- 使用
while (left <= right)
。这是因为当left
和right
相等时,它们指向的数组元素可能是要查找的目标元素。
- 使用
- 中间索引计算:
- 使用
left + ((right - left) / 2)
来计算middle
,这样可以避免整数溢出。
- 使用
- 元素比较与指针更新:
- 如果
nums[middle] == target
,则找到目标元素,直接返回middle
。 - 如果
nums[middle] < target
,则更新left = middle + 1
,继续在右侧搜索。 - 如果
nums[middle] > target
,则更新right = middle - 1
,继续在左侧搜索。
- 如果
- 返回结果:
- 如果循环结束后仍未找到目标元素,返回 -1 。
- 特殊情况处理:
- 如果数组为空,可以在开始时检查,并直接返回-1。
代码如下:
- 如果数组为空,可以在开始时检查,并直接返回-1。
class Solution {
public int search(int[] nums, int target) {
if (nums.length == 0){
return -1;
}
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if (nums[mid] > target){
right = mid - 1;
}else if (nums[mid] < target){
left = mid + 1;
}else{
return mid;
}
}
return -1;
}
}
二分法第二种写法
target 是在左闭右开的区间里查找,即[left,right)
。
- 循环条件:
- 使用
while (left < right)
。因为区间是左闭右开的,所以当 left 等于 right 时,实际上已经没有元素可以查找了,循环应该终止。
- 使用
- 中间索引计算:
- 中间索引的计算方式与左闭右闭区间相同,使用
left + (right - left) / 2;
来防止整数溢出。
- 中间索引的计算方式与左闭右闭区间相同,使用
- 元素比较与指针更新:
- 如果
nums[middle] == target
,则找到目标元素,直接返回middle
。 - 如果
nums[middle] < target
,则更新left = middle + 1
,继续在右侧搜索。 - 如果
nums[middle] > target
,则更新right = middle
。 - 注意:这里是
right = middle
而不是right = middle - 1
,因为区间是左闭右开的。
- 如果
- 返回结果:
- 如果循环结束后仍未找到目标元素,则返回 -1。
- 特殊情况处理:
- 与左闭右闭区间一样,开始处检查数组是否为空,并直接返回 -1。
代码如下:
- 与左闭右闭区间一样,开始处检查数组是否为空,并直接返回 -1。
class Solution {
public int search(int[] nums, int target) {
if (nums.length == 0){
return -1;
}
int left = 0;
int right = nums.length - 1;
while(left < right){
int mid = left + (right - left) / 2;
if (nums[mid] > target){
right = mid;
}else if (nums[mid] < target){
left = mid + 1;
}else{
return mid;
}
}
return -1;
}
}
螺旋矩阵 II
给你一个正整数 n
,生成一个包含 1
到 n2
所有元素,且元素按顺时针顺序螺旋排列的 n x n
正方形矩阵 matrix
。
示例1:
输入:
n = 3
输出:[[1,2,3],[8,9,4],[7,6,5]]
示例2:
输入:
n = 1
输出:[[1]]
提示 :1 <= n <= 20
思路
这一题很考验做题者对代码的掌控能力。我们使用左闭右开原则进行绘图。
如图所示,我们每次遍历一条边,都是以左闭右开来遍历,这样就不容易出错。
如果是奇数圈的话,我们就对其进行判断,手动将其填充即可。
代码如下:
class Solution {
public int[][] generateMatrix(int n) {
// 初始化一个要填充的目标矩阵
int[][] matrix = new int[n][n];
// 定义螺旋开始的行和列,标识我们在哪里开始填充矩阵
int rowStart = 0;
int columnStart = 0;
// 定义螺旋的层级,标识我们正在填充的螺旋层级
int level = 1;
// 定义边界的偏移量,计算在每一层螺旋中,需要填充的行或列的范围
int offset = 1;
// 定义要填充的数字
int number = 1;
// 定义行和列的索引
int row, column;
// 当螺旋层级小于等于 n / 2 时,进行螺旋填充
while(level <= n / 2){
// 从左到右填充上方的行
for(column = columnStart; column < n - offset; column++){
matrix[rowStart][column] = number++;
}
// 从上到下填充右方的列
for(row = rowStart; row < n - offset; row++){
matrix[row][column] = number++;
}
// 从右到左填充下方的行
for(; column > columnStart; column--){
matrix[row][column] = number++;
}
// 从下到上填充左方的列
for(; row > rowStart; row--){
matrix[row][column] = number++;
}
// 更新螺旋开始的行和列,螺旋层级和边界偏移量
rowStart++;
columnStart++;
level++;
offset++;
}
// 如果 n 是奇数,填充中心的元素
if(n % 2 != 0){
matrix[rowStart][columnStart] = number;
}
return matrix;
}
}
为什么循环是 n/2 次:
主要是理解螺旋填充的过程。在一个n x n的矩阵中,螺旋填充的过程可以看作是一层一层向内进行的。每一层都是一个环形,从外层开始,逐渐向内层进行。
因为对于一个n x n的矩阵,最多有n / 2层环形(如果n是奇数,中心的单个元素也被视为一层)。
例如,当n = 3时,矩阵如下:
1 2 3
8 9 4
7 6 5
这个矩阵有两层环形,外层环形包含元素1, 2, 3, 4, 5, 6, 7, 8,内层环形(一个点)包含元素9。
所以,当螺旋层级小于等于n / 2时,我们就继续进行螺旋填充,直到所有的环形层级都被填充完毕。
移除元素
给你一个数组 nums
和一个值 val
,你需要 原地 移除所有数值等于 val
的元素。元素的顺序可能发生改变。然后返回 nums
中与 val
不同的元素的数量。
假设 nums
中不等于 val
的元素数量为 k
,要通过此题,您需要执行以下操作:
- 更改
nums
数组,使nums
的前k
个元素包含不等于val
的元素。nums
的其余元素和nums
的大小并不重要。 - 返回
k
。
示例 1:
输入: nums = [3,2,2,3], val = 3
输出: 2, nums = [2,2,,]
解释: 你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要(因此它们并不计入评测)。
示例 2:
输入: nums = [0,1,2,2,3,0,4,2], val = 2
输出: 5, nums = [0,1,4,0,3,,,]
解释: 你的函数应该返回 k = 5,并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要(因此它们并不计入评测)。
提示:
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
思路
这一道题呢,我使用的方法有两种:
- 暴力法
- 双指针法(快慢指针)
暴力解法(不推荐)
直接两层for循环,外层循环遍历数组元素,内层循环更新数组元素。如下图:
C++:
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int currentSize = nums.size(); // 当前数组的大小
for (int i = 0; i < currentSize; i++) {
if (nums[i] == val) { // 如果当前元素是需要移除的元素
// 内部循环:将数组中后续的所有元素向前移动一位
for (int j = i + 1; j < currentSize; j++) {
nums[j - 1] = nums[j]; // 将位置j的元素移动到位置j-1
}
i--; // 因为当前位置i的元素已经被移除,需将i回退一位,以检查新的当前元素
currentSize--; // 数组大小减一,因移除一个元素
}
}
return currentSize; // 返回移除指定元素后的数组大小
}
};
// 时间复杂度:O(n^2)
// 空间复杂度:O(1)
双指针法
可以定义一个快指针和一个慢指针在一个for循环下完成两个for循环所做的事。
- 快指针:负责遍历整个数组。目的是找到新的数组的元素,即不包含目标元素
val
的所有元素。 - 慢指针:指向要更新的位置
如下图:
C++:
class Solution {
public:
int removeElement(std::vector<int>& nums, int val) {
int i = 0; // 慢指针
for (int j = 0; j < nums.size(); j++) { // 快指针
if (nums[j] != val) {
nums[i] = nums[j];
i++;
}
}
return i;
}
};
// 时间复杂度:O(n)
// 空间复杂度:O(1)