随想录Day1|704. 二分查找、27. 移除元素
704. 二分查找
给定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. 移除元素
给定一个数组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;
}
碎碎念
做题用时:30分钟
今天是算法训练营第一天,主要时间花给了博客园的外观搭建工作,终于把它调到较为满意了,这个可能花了五六个小时,对网页方面确实不太熟悉。但是拥有了自己的小世界真的非常幸福!
看文档也花了挺久,但是不得不说卡尔的文档写得真好啊,而且这也是第一天的固定支出,明天一定会顺利很多!今天的题目就是用的VSCode LeetCode插件,比直接在网页上敲要顺手多了,还得是IDE。
以后粉字就是题目,蓝字用于纠正,绿字表示强调。今天比较顺利,之后不顺利的时候我会更详细地记录我想错的地方和遇到的困难。
标签:index,27,target,nums,int,元素,随想录,数组,移除 From: https://www.cnblogs.com/alouette/p/17718477.html