代码随想录算法训练营第一天 | leetcode：二分法，移除元素

_zzh 的个人博客 / 276 / 0 / 创建于 3个月前 / 更新于 2个月前

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;
    }
}