代码随想录算法训练营第一天 | leetcode：二分法，移除元素
0 / 0 / 创建于 1年前 /
_zzh 的个人博客
Problem: 704. 二分查找
需要注意的问题
- 确认题目给定的条件是否满足使用二分法，以及给定的区间是左闭右闭[0,n]，还是左闭右开[0,n)。
- 当为左闭右闭时，初始right值为多少，当为左闭右开时，是多少？
- 当为左闭右闭时，while()里面的循环条件是什么，当为左闭右开时，是什么？
- 当为左闭右闭时，target < mid，需要更新右边界时，right值需要怎么更新？当为左闭右开时，right值需要怎么更新？
- 更新边界时需要遵循题目所给的区间规则（左闭右闭/左闭右开）。不然下次循环while（）
- 这道题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件。
解题方法
- 已知左闭右闭是包含两边的意思，left从0开始，故right需要做size-1操作。左闭右开是包含左边不包含右边的意思，left从0开始，故right为size不需要做size-1操作。
- 确定while()循环条件：可以用举例法进行验证。如当为左闭右闭时，left<=right [1,1]是否成立？当为左闭右开时，left<=right [1,1)是否成立？这样就能确定循环条件了。
- 当给定区间为左闭右闭，target < mid，需要更新右边界时，遵循区间规则，更新区间也应该为左闭右闭，但是此时条件已确定target < mid，故mid必然不等于target。所以此时，更新右边界的时候需要把mid剔除前移一位。即：right=mid-1。当target > mid，需要更新左边界时，同理。即left = mid + 1;
- 当给定区间为左闭右开，target < mid，需要更新右边界时，遵循区间规则，更新区间也应该为左闭右开，此时条件已确定target < mid，故mid不应该被包含在新区间中，而左闭右开正好是不包含右边界。所以此时，更新右边界的时候就可以直接使用mid。即：right=mid。当target > mid，需要更新左边界时，同3。即left = mid + 1;
复杂度
时间复杂度:
O(logn)
空间复杂度:
O(1)
左闭右闭写法
class Solution
{
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer
*/
function search($nums, $target)
{
$len = count($nums);
//判断空数组
if ($len <= 0) {
return -1;
}
$left = 0;
//区间为左闭右闭需要-1
$right = count($nums) - 1;
//区间为左闭右闭需要 条件为<=
while ($left <= $right) {
//对于二进制的正数来说，右移x位相当于除以2的x几次方，所以右移一位等于÷2
//用位运算的好处是比直接相除的操作快
$mid = $left + (($right - $left) >> 1);
// $mid = $left + (($right - $left) / 2);
if ($nums[$mid] > $target) {
//更新右边界，右区间为闭合，右边界需要-1，跳过mid
$right = $mid - 1;
} elseif ($nums[$mid] < $target) {
//更新左边界，左区间为闭合，左边界需要+1，跳过mid
$left = $mid + 1;
} else {
return $mid;
}
}
return -1;
}
}左闭右开写法
class Solution
{
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer
*/
function search($nums, $target)
{
$len = count($nums);
//判断空数组
if ($len <= 0) {
return -1;
}
$left = 0;
//区间为左闭右开不需要-1
$right = count($nums);
//区间为左闭右闭需要 条件为<
while ($left < $right) {
//对于二进制的正数来说，右移x位相当于除以2的x几次方，所以右移一位等于÷2
//用位运算的好处是比直接相除的操作快
$mid = $left + (($right - $left) >> 1);
// $mid = $left + (($right - $left) / 2);
if ($nums[$mid] > $target) {
//更新右边界，右区间为开，右边界不需要-1
$right = $mid;
} elseif ($nums[$mid] < $target) {
//更新左边界，左区间为闭合，左边界需要+1，跳过mid
$left = $mid + 1;
} else {
return $mid;
}
}
return -1;
}
}Problem: 27. 移除元素
需要注意的问题
- 题目指出不要使用额外的数组空间，必须仅使用 O(1) 额外空间并 原地 修改输入数组。
- 你不需要考虑数组中超出新长度后面的元素。
解题方法
- 使用快慢指针，快指针用作遍历目标数组；慢指针用作更新数组。
- 当快指针遍历数组时，不等于目标值的数值，赋值给慢指针所在的下标位置，同时慢指针向前移动。
- 当快指针遍历找到目标值时，慢指针不动，快指针向前移动，从而形成对目标数据val的覆盖。
复杂度
时间复杂度:
O(n)
空间复杂度:
O(1)
Code
class Solution
{
/**
* @param Integer[] $nums
* @param Integer $val
* @return Integer
*/
function removeElement(&$nums, $val)
{
$slow = 0; //定义慢指针更新数据
//定义快指针遍历数组
for ($fast = 0; $fast < count($nums); $fast++) {
if ($nums[$fast] != $val) {
//当快指针值不等于目标值，则更新数值到慢指针处。慢指针++。
$nums[$slow] = $nums[$fast];
$slow++;
}
}
return $slow;
}
}本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号