当前位置:   article > 正文

代码随想录算法训练营第一天|LeetCode704.二分查找、LeetCode27.移除元素。_代码随想录算法训练营第一天|leetcode 704.二分查找、27移除元素

代码随想录算法训练营第一天|leetcode 704.二分查找、27移除元素

今日学习文章:数组理论基础

LeetCode704.二分查找

题目链接LeetCode704.二分查找

二分法适用:有序且无重复的数组下标查找 

时间复杂度:O(logn)    

空间复杂度:O(1)

思路:利用循环,先寻找到数组的中间值 nums[mid] ,再将其与target进行比较,若 nums[mid] > target 则我们所找的值在中间值的左边;此时,我们将距中间值左边一个单位的元素作为新的右端值,之后再求中间值。若nums[mid] < target 则我们所找的值在中间值的右边;此时,我们将距中间值右边一个单位的元素作为新的左端值,之后再求中间值。若nums[mid] = target 则得到我们所要查找的目标值的下标mid。以此类推,通过不断二分来寻找目标元素下标值。

左闭右闭: 

  1. class Solution {
  2. public:
  3. int search(vector<int>& nums, int target) {
  4. int left = 0;
  5. int right = nums.size() - 1;
  6. int mid = 0;
  7. while(left <= right)
  8. {
  9. mid = (left + right)/2;
  10. if(nums[mid] > target)
  11. {
  12. right = mid - 1;
  13. }
  14. else if(nums[mid] < target)
  15. {
  16. left = mid + 1;
  17. }
  18. else
  19. {
  20. return mid;
  21. }
  22. }
  23. return -1;
  24. }
  25. };

左闭右开:

  1. class Solution {
  2. public:
  3. int search(vector<int>& nums, int target) {
  4. int left = 0;
  5. int right = nums.size();
  6. int mid = 0;
  7. while(left < right)
  8. {
  9. mid = (left + right)/2;
  10. if(nums[mid] > target)
  11. {
  12. right = mid;
  13. }
  14. else if(nums[mid] < target)
  15. {
  16. left = mid + 1;
  17. }
  18. else
  19. {
  20. return mid;
  21. }
  22. }
  23. return -1;
  24. }
  25. };

小结:

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.移除元素

题目链接LeetCode27.移除元素

 暴力解法

  1. class Solution {
  2. public:
  3. int removeElement(vector<int>& nums, int val) {
  4. int size = nums.size();
  5. for(int i = 0;i < size;i++)
  6. {
  7. if(nums[i] == val)
  8. {
  9. for(int j = i+1;j < size;j++)
  10. {
  11. nums[j - 1] = nums[j];
  12. }
  13. i--;
  14. size--;
  15. }
  16. }
  17. return size;
  18. }
  19. };

时间复杂度:O(n²)    

空间复杂度:O(1) 

思路:先算出数组总长度,之后用两个for循环进行遍历比较,如果数组元素等于目标值,则将该数组后一个元素覆盖当前数组元素,并将数组总长度减一。最后得出进行移除后数组的长度与新的数组。

小结:该解法没有什么太多的技巧,进行遍历即可,但是所占用的内存大,时间复杂度更高,不推荐使用。

快慢指针

  1. class Solution {
  2. public:
  3. int removeElement(vector<int>& nums, int val) {
  4. int size = nums.size();
  5. int slow = 0;
  6. for(int fast = 0;fast < size;fast++)
  7. {
  8. if(nums[fast] != val)
  9. {
  10. nums[slow++] = nums[fast];
  11. }
  12. }
  13. return slow;
  14. }
  15. };

时间复杂度:O(n)     

空间复杂度:O(1) 

思路:分别设定快指针fast用于与目标值进行比较;慢指针slow用于更新数组元素;从而将两个for循环减少为一个for循环。

小结:快指针和慢指针在应用中的作用不同:快指针通过对比寻找新数组的元素,慢指针则接收新数组的元素并更新新数组下标位置。本质上是对同一个数组进行操作,而原数组元素的相对位置并没有发生改变;该解法有效降低了时间复杂度。

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号