赞
踩
题目链接:LeetCode704.二分查找
二分法适用:有序且无重复的数组下标查找
时间复杂度:O(logn)
空间复杂度:O(1)
思路:利用循环,先寻找到数组的中间值 nums[mid] ,再将其与target进行比较,若 nums[mid] > target 则我们所找的值在中间值的左边;此时,我们将距中间值左边一个单位的元素作为新的右端值,之后再求中间值。若nums[mid] < target 则我们所找的值在中间值的右边;此时,我们将距中间值右边一个单位的元素作为新的左端值,之后再求中间值。若nums[mid] = target 则得到我们所要查找的目标值的下标mid。以此类推,通过不断二分来寻找目标元素下标值。
左闭右闭:
- class Solution {
- public:
- int search(vector<int>& nums, int target) {
- int left = 0;
- int right = nums.size() - 1;
- int mid = 0;
- while(left <= right)
- {
- mid = (left + right)/2;
- if(nums[mid] > target)
- {
- right = mid - 1;
- }
- else if(nums[mid] < target)
- {
- left = mid + 1;
- }
- else
- {
- return mid;
- }
- }
- return -1;
- }
- };

左闭右开:
- class Solution {
- public:
- int search(vector<int>& nums, int target) {
- int left = 0;
- int right = nums.size();
- int mid = 0;
- while(left < right)
- {
- mid = (left + right)/2;
- if(nums[mid] > target)
- {
- right = mid;
- }
- else if(nums[mid] < target)
- {
- left = mid + 1;
- }
- else
- {
- return mid;
- }
- }
- return -1;
- }
- };
-

小结:
1.当target处于左闭右闭区间[left,right]时,存在left == right的情况,因此循环条件便需要left <= right;此时,因右端为闭区间,数组右端元素的下标right不能越界,故right的值为数组长度减一,即 right = size - 1。
2.当target处于左闭右开区间[left,right)时,此时不存在left == right的情况,只需要循环条件为left < right便可执行循环,而因右端为开区间,数组右端元素的下标不等于right,故right的值可以为数组长度,即 right = size。
题目链接:LeetCode27.移除元素
暴力解法:
- class Solution {
- public:
- int removeElement(vector<int>& nums, int val) {
- int size = nums.size();
- for(int i = 0;i < size;i++)
- {
- if(nums[i] == val)
- {
- for(int j = i+1;j < size;j++)
- {
- nums[j - 1] = nums[j];
- }
- i--;
- size--;
- }
- }
- return size;
- }
- };
-

时间复杂度:O(n²)
空间复杂度:O(1)
思路:先算出数组总长度,之后用两个for循环进行遍历比较,如果数组元素等于目标值,则将该数组后一个元素覆盖当前数组元素,并将数组总长度减一。最后得出进行移除后数组的长度与新的数组。
小结:该解法没有什么太多的技巧,进行遍历即可,但是所占用的内存大,时间复杂度更高,不推荐使用。
快慢指针:
- class Solution {
- public:
- int removeElement(vector<int>& nums, int val) {
- int size = nums.size();
- int slow = 0;
- for(int fast = 0;fast < size;fast++)
- {
- if(nums[fast] != val)
- {
- nums[slow++] = nums[fast];
- }
- }
- return slow;
- }
- };
时间复杂度:O(n)
空间复杂度:O(1)
思路:分别设定快指针fast用于与目标值进行比较;慢指针slow用于更新数组元素;从而将两个for循环减少为一个for循环。
小结:快指针和慢指针在应用中的作用不同:快指针通过对比寻找新数组的元素,慢指针则接收新数组的元素并更新新数组下标位置。本质上是对同一个数组进行操作,而原数组元素的相对位置并没有发生改变;该解法有效降低了时间复杂度。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。