704.二分查找

题目链接：二分查找

思路：

1.从头开始遍历，首先如果不用二分查找法，最容易想到的就是直接暴力查找，时间复杂度为O(n)直接从头开始遍历一便就行。这样如果数据量庞大会运行时间较长。

2.二分法，时间复杂度为O(logn)，相比暴力解运行速度会更快，二分法编写时，需要注意每一次查找时的左右两个端点，和前提条件。
（1）左闭右闭区间，左右端点都可以取到
·while(left<=right)
·每一次二分后，若target在左边区间，则right=mid-1，若target在右边区间，则left=mid+1。
（2）左闭右开区间，只有左端点可以取到
·while(left ·每一次二分后，若target在左边区间，则right=mid，若target在右边区间，则left=mid+1。

暴力解代码

int search(int* nums, int numsSize, int target){/*暴力解*/    int i=0;for(;i<numsSize;i++){if(*(nums+i)==target)break;}if(i==numsSize)return -1;else return i;      
}

二分法代码

左闭右闭区间

int search(int* nums, int numsSize, int target){int left=0,right=numsSize-1;int mid=(left+right)/2;int flag=0;while(left<=right){mid=(left+right)/2;if(target>nums[mid])left=mid+1;else if(target<nums[mid])right=mid-1;else if(target==nums[mid])return mid;}return -1;     
}

左闭右开区间

int search(int* nums, int numsSize, int target){int left=0,right=numsSize-1;int mid=(left+right)/2;while(left<right){mid=(left+right)/2;if(target>nums[mid])left=mid+1;//left取得到得，要mid+1，else if(target<nums[mid])right=mid;//right是取不到的可以直接等于midelse if(target==nums[mid])return mid;}return -1;         
}

27.移除元素

题目链接移除元素

思路：

1.暴力解法，从头到尾遍历数组，只要发现要移除的目标元素，就开始从该位置后一位开始依次往前进行覆盖，每覆盖完一轮就数组长度减1。

2.双指针法（快慢指针法），即用两个下标，分别称为slow下标和quick下标，slow用来标记最后剔除目标元素的新数组下标，quick用来遍历整个数组，找到非目标元素，存入到slow下标的元素位置，每次quick指的是非目标元素，就nums[slow++]=nums[quick]

暴力解代码

int removeElement(int* nums, int numsSize, int val){for(int i=0;i<numsSize;i++){if(nums[i]==val){for(int j=i+1;j<numsSize;j++)nums[j-1]=nums[j];i--;//因为后面的往前面覆盖了numsSize--;}}return numsSize;
}

双指针法代码

int removeElement(int* nums, int numsSize, int val){int slow=0;for(int quick=0;quick<numsSize;quick++){if(nums[quick]!=val){ nums[slow++]=nums[quick];}} return slow;
}

今日总结：

两道题目一开始，我想都没想全用的暴力解，然后第一道题目的二分法，我写起来完全错误，大方向思路知道，但是一些关键核心代码写错了，尤其是while循环里面忘记写每一次二分后的mid式子了。。。。。。第二道题，双指针法一开始没搞懂，后面看视频懂的，简洁说就是，不是目标元素的跳过不写入“新”数组，是目标元素的跳过。今天两道题是完全弄懂了，清清楚楚，明明白白

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！