题目链接:
704. 二分查找 - https://leetcode.cn/problems/binary-search/description/
27. 移除元素 - https://leetcode.cn/problems/remove-element/description/文章学习链接:https://programmercarl.com/数组理论基础.html
视频学习链接:https://www.bilibili.com/video/BV1fA4y1o715
704. 二分查找
思路:由题意的,是二分查找,所以直接使用了二分查找的方法。
二分查找
使用条件
-
用于查找的内容逻辑上来说是需要有序的
-
查找的数量只能是一个,而不是多个(多个返回结果可能不一样)
步骤:
确定一个左边界,一个右边界,判断要求的值是否在范围内,如果不在,是大于目标值还是小于目标值,然后以此调节范围
解答代码
class Solution {
public int search(int[] nums, int target) {
// 判断数组非空 和 简单的范围判断(因为有序)
if(nums == null || target > nums[nums.length -1] || target < nums[0]){
return -1;
}
// 给定初值边界
int left = 0;
int right = nums.length;
int mid ;
// 当左边大于右边,跳出循环
while(left < right){
mid = (right + left)/2;
if(nums[mid] == target){
return mid;
}
if(nums[mid] > target){ // target 在左区间,在[left, middle)中
right = mid;
continue;
}
if(nums[mid] < target){ // target 在右区间,在[middle + 1, right)中
left = mid +1 ;
continue;
}
}
return -1;
}
}
出现的问题:
一开始超出时间限制了嘞 >.<
注意点:
1、mid = (right + left)/2 是加,不是减,是求两个点之间的中值
2、left = mid + 1 那里和 right = mid 区别
二分法有两种写法
一种取值是left、right是闭区间的,即left和right都在数组内,[left,right]
一种取值是left、right是左闭右开,即[left,right)
当选择第二种时注意,让right一直处于开区间的那,(由第二个注意点那里保证)。
27. 移除元素
思路:暴力破解,双指针法
1、暴力破解
步骤:逐个匹配,当匹配到和给定的val值一样的时候,将后面的元素都往前提一个元素。两层for循环,一个for循环遍历数组元素 ,第二个for循环更新数组。
代码:
class Solution {
public int removeElement(int[] nums, int val) {
int target = 0; //记录val值的个数
int len = nums.length; // 原数组长度
for(int i = 0 ; i< len;i++){ //i<len 最大可到 len - 1 (原数组最大下标)
if(nums[i] == val){ //等于则将后面的元素都往前移
for(int j = i; j< len - 1; j++){ // j<len-1 最大可到 len - 2 ,防止j+1下标越界,当进入到这里面的时候也只少会有一个val
nums[j] = nums[j+1];
}
target++;
i--; // 为了判断前移的第一个元素是否等于val
}
if(i == len - target - 1){ // 当长度到len - target - 1 就不用判断了
break;
}
}
return len - target;
}
}
注意点
1、匹配时候同时出现两个val值连在一起时
2、给定的数组只要一个元素或是没有元素的时候
2、双指针法
双指针法(快慢指针法): 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
步骤:
定义快慢指针
快指针:寻找新数组的元素 ,新数组就是不含有目标元素的数组
慢指针:指向更新 新数组下标的位置
class Solution {
public int removeElement(int[] nums, int val) {
int slowIndex = 0;
for(int fastIndex = 0,len = nums.length;fastIndex < len;fastIndex++){
if(nums[fastIndex] != val){
nums[slowIndex] = nums[fastIndex];
slowIndex++;
}
}
return slowIndex;
}
}
或者相向,(题目提示说可以无序)
收获
复习了双指针法
很久之前写过,以为重写应该会很简单,结果都没有一次写出来
标签:right,nums,int,随想录,mid,27,数组,移除,left From: https://www.cnblogs.com/slothion/p/18085605ps:一刷以完成题目为标准,除了指定说要学的方法,多做题,各种解题思路等二刷再去一个个看