【代码训练营】day1|704.二分查找&27.移除元素-创新互联
目录
本文题目:【代码训练营】day1|704.二分查找&27.移除元素-创新互联
网页路径:http://myzitong.com/article/jdhjp.html
- 数组基础
- 数组理论知识
- 二分查找 Leetcode704
- 题目连接:[二分查找 Leetcode704 - 简单](https://leetcode.cn/problems/binary-search/)
- 思路
- java代码
- 总结
- 移除元素 Leetcode27
- 题目链接:[移除元素 Leetcode27 - 简单](https://leetcode.cn/problems/remove-element/)
- 思路
- java代码
- 总结
注意:
- 数组的下标都从0开始
- 数组的内存地址是连续的
由于数组
地址是连续的
,所以在删除或插入元素的时候,都要移动后面的元素
对于二维数组的话,C++是地址是连续的,java不连续。 java的地址如下图:
二分查找 Leetcode704 题目连接:二分查找 Leetcode704 - 简单 思路本题主要有两种解法:一是左闭右闭[ , ]
,一种是左闭右开[ , )
,在大部分的题型中都采用左闭右开的方法。
1、左闭右闭
public int search(int[] nums, int target) { int left = 0;
int right = nums.length - 1;
// 左闭右闭的情况可以取到中间的值
//如[01234],当left=2 right=2 target=2,若letf // int middle = (left + right) / 2; 可能会溢出
int middle = left + ((right - left)>>1);
if (nums[middle]< target){// [,target]目标值在右边
left = middle + 1; // 调整左区间[middle+1,],左为闭区间 要 +1
}else if(nums[middle] >target){// [target,]目标值在左边
right = middle - 1; // 调整右区间[,middle-1],右为闭区间 要 -1
}else { return middle; // 找到则返回下标
}
}
return -1;
}
2、左闭右开
public int search(int[] nums, int target) {int left = 0;
int right = nums.length; // 这里不-1
// 因为右边取不到,所以不用取等
//如[01234],当target=2 left=2 right=3时就返回了,所以不用取等
while (left< right){int middle = left + ((right - left) >>1);
if (nums[middle]< target){// [,target)在目标值右边
left = middle + 1; // 左为闭区间要 + 1
}else if(nums[middle] >target){// [target,)在目标值左边
right = middle; // 右边取不到的,直接取等
}else {return middle;
}
}
return -1;
}
总结1、遇到问题:在写左闭右开的时提交一直不对,是由于没考虑到right = nums.length
此时右区间不用减一,因为右区间取不到。
2、注意: 取中间值最好用位运算middle = left + ((right - left) >>1)
,虽然直接写middle = (left + right) / 2
也能通过,但是就怕其他情况出现溢出。还有一个注意点就是middle的位置
和left ?= right
此题不能有额外的数组空间,也就是进行原地修改,修改后直接返回数组长度就实行了。所以把需要修改元素位置找到,后面的再依次填充就好了
- - 双指针解法
快指针:指向数组下标,若不是目标值就更新,是目标值就跳过。
慢指针:指向更新数组的下标
1、暴力解法
public int removeElement(int[] nums, int val) { int count = nums.length;
// i if (nums[i] == val){ for (int j = i+1; j< count; j++) { nums[j-1] = nums[j];
}
// System.out.println("看一下nums" + Arrays.toString(nums));
i--;
count--;
}
}
return count;
}
2、双指针(推荐)
public int removeElement(int[] nums, int val) {// 慢指针,用于存储新的数组元素,每次储存一位就后移一位
int slow = 0;
// 快指针,用于复制原数组里面不包含val的数
for (int fast = 0; fast< nums.length; fast++) {if (nums[fast] != val){nums[slow++] = nums[fast];
}
}
return slow;
}
总结1、遇到的问题: 在写暴力的时候一直输出错误,错在我一开始写的循环结束条件为i< nums.length
,但是这样就没有考虑到每次后移最后就是目标值,这样就会进入死循环。
2、熟练使用双指针可解决大部分数组的题,若不太会就画出图或是打输出语句。
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
本文题目:【代码训练营】day1|704.二分查找&27.移除元素-创新互联
网页路径:http://myzitong.com/article/jdhjp.html