随想录Day1|704. 二分查找、27. 移除元素

704. 二分查找

LeetCode题目

文章讲解

视频讲解

给定n个元素升序的整形数组nums和一个目标值target，写一个函数搜索nums中的target，如果存在目标值则返回下标，否则返回-1。其中nums中的元素不重复，n在[1, 10000]之间，nums的每个元素都在[-9999, 9999]之间。

第一想法和纠正

可以用整形数组，直接10000个int。（实际上并没用到这个）

二分查找，需要用到递归，核心函数输入数组的起止位置（左闭右开），比较target和中间值，如果中间值更大则再调用该函数比较左半段，否则比较右半段；如果相等则找到。必须满足l_index + 1 <= r_index（取等于的时候，数组恰好有一个值），如果这时还不相等，则没有target，应该返回-1。

看到代码的想法

按引用传递了nums，但是我们并不应修改数组，此处应该是为了节省空间。

用于递归的函数要自己在外面另写，因为需要传入左右下标。如果把递归用的核心函数叫做search_index，~~它应该在左下标大于右下标的时候返回。~~（实际上调用这个函数的时候一定可以保证l_index + 1 <= r_index，无需在此特判。）

此处需要返回什么？是单纯return还是需要返回某个值？下标如何被传递到search原函数中（作为它的返回值）？

所以需要返回下标，如果是比较左半边或右半边区间则返回调用的search_index的返回值，否则返回m_index。

然后AC了！

int search(vector<int> &nums, int target)
{
    int len = nums.size();
    int index = search_index(nums, 0, len, target);
    return index;
}

int search_index(vector<int> &nums, int l_index, int r_index, int target)
{
    int index;

    if (l_index + 1 == r_index)
    {
        if (nums[l_index] != target)
            return -1;
        return l_index;
    }

    int m_index = (l_index + r_index) / 2;
    int mvalue = nums[m_index];
    int lvalue = nums[l_index];
    int rvalue = nums[r_index];

    if (mvalue == target)
        return m_index;
    if (mvalue > target)
    {
        index = search_index(nums, l_index, m_index, target);
        return index;
    }
    else
    {
        index = search_index(nums, m_index, r_index, target);
        return index;
    }

看完随想录题解的想法

我想复杂啦！直接在while循环中就好，不需要额外拆出来一个函数。具体代码见文章讲解。

27. 移除元素

LeetCode题目

文章讲解

视频讲解

给定一个数组nums和一个值val，原地移除所有数值等于val的元素，返回数组的新长度。数据满足：

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

第一想法

只需要考虑新长度范围内的元素，说明额外辅助空间可以利用数组的尾部。如果按照最朴素的想法，从左到右遍历数组，遇到了等于val的元素就把它后面的全部元素往左移一个，时间复杂度是$O(n^2)$。

看完随想录题解的想法

愣住了，于是看了文章讲解，采用快慢指针法，其中：

快指针：寻找新数组的元素，新数组就是不含有目标元素的数组

慢指针：指向更新新数组下标的位置

恍然大悟，也就是：

当前元素等于val时，只移动快指针
不等于时，把快指针指向的元素填入慢指针处，然后快慢指针均向后一位。

先填后移是为了每次快慢指针都指向将要被操作的位置，这样最后可以直接返回slow作为新数组长度。

int removeElement(vector<int> &nums, int val)
{
    int fast = 0, slow = 0;
    int len = nums.size();
    for (int i = 0; i < len; i++)
    {
        if (nums[i] == val)
            fast++;
        else
            nums[slow++] = nums[fast++];
    }
    return slow;
}