代码随想录算法训练营第一天|704 二分查找。27移除元素
704.二分查找
题目
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
题解
二分查找相对来说比较简单,二分查找的前提条件是有序的,并且无重复。二分查找顾名思义,核心就是需要进行对半拆分,操作左右位以及中间位,最后在不断缩小的范围内将目标值target查询出来
class Solution {
public int search(int[] nums, int target) {
//一开始,预先定义好左右两个边界值
int left = 0 ;
int right = nums.length-1;
while(left <= right){
//在每次遍历中都获取中间位,(left right 可能会内存溢出)
int middle = left (right -left)/2;
// 将目标值和数组中的中间值做对比,缩小数据范围
if(target < nums[middle]){
//目标值在左边,则将middle这是为终点,为什么是-1,因为while条件内已经包含了边界right值
right = middle - 1;
}else if(target > nums[middle]){
//目标值在右边,则将middle设置为起点
left = middle 1;
}else{
return middle;
}
}
return -1;
}
}
27.移除元素
题目
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
你不需要考虑数组中超出新长度后面的元素
题解
前提知识:数组的元素在内存地址中是连续的,不能单独删除数组中的某个元素,只能覆盖
题解一:暴力解法
两个for循环,一个for遍历数组元素,一个for将等于val之后的元素都前移一位
class Solution {
public int removeElement(int[] nums, int val) {
//记录数组长度,因为后面的操作会修改数组长度
int size = nums.length;
//第一层遍历,将等于val的元素找出来
for (int i = 0; i < size; i ) {
if (nums[i] == val) {
//第二层遍历,将val之后的所有元素都往前赋值一位
for (int j = i 1; j < size; j ) {
nums[j - 1] = nums[j];
}
//因为i所在的值已经被前一个覆盖,所以i需要向前一位,以便下次i 循环
i--;
//整个数组长度也跟着减去一个
size--;
}
}
return size;
}
}
题解二:快慢指针
核心:快指针筛选全部元素,慢指针指向新的数组元素
//事先定义慢指针,因为慢指针会变化
int slow = 0;
for (int fast = 0; fast < nums.length; fast ) {
//把不含有目标元素数组的位置用慢指针定位出来
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow ;
}
}
return slow;
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgghjcj
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13