算法学习第一天-二分法及双指针法

今日任务

数组理论基础，704. 二分查找，27. 移除元素

704. 二分查找
     题目链接：https://leetcode.cn/problems/binary-search/
     文章讲解：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html
     视频讲解：https://www.bilibili.com/video/BV1fA4y1o715

705. 移除元素
     题目链接：https://leetcode.cn/problems/remove-element/
     文章讲解：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
     视频讲解：https://www.bilibili.com/video/BV12A4y1Z7LP

704实现代码

class Solution {
 public:
  //28ms 29.23MB
  int search(vector<int> &nums, int target) {
      int n = 0;//注意初始化
      for (auto it = nums.begin(); it != nums.end(); ++it) {
          if (*it == target)
              return n;
          n += 1;
      }
      return -1;
  }
  //33ms 29.27MB
  int search_two_part(vector<int> &nums, int target) {
      int left_index = 0;
      int right_index = nums.size() - 1;
      while (left_index <= right_index) {
          int mid_index = (left_index + right_index) / 2;
          if (nums[mid_index] < target)
              left_index = mid_index + 1;
          else if (nums[mid_index] > target)
              right_index = mid_index - 1;
          else
              return mid_index;
      }
      return -1;
  }
};

27实现代码

class Solution_27 {
 public:
  //10ms 10.16MB
  // 时间复杂度：O(n^2)
// 空间复杂度：O(1)
  int removeElement(vector<int> &nums, int val) {
      int vec_size = nums.size();
      for (int i = 0; i < vec_size;) {
          if (nums[i] == val) {
              vec_size -= 1;//去掉该元素，数组长度减一
              for (int j = i; j < vec_size; ++j) {
                  nums[j] = nums[j + 1];//数组只能覆盖
              }
          } else
              ++i;
      }
      return vec_size;
  }
// 时间复杂度：O(n)
// 空间复杂度：O(1)
//跳过需要删除的元素
  int removeElement_double_points(vector<int> &nums, int val) {
      int fast = 0;
      int slow = 0;
      for(; fast < nums.size(); ++fast){
          if(nums[fast] != val){
              nums[slow++] = nums[fast];
          }
      }
      return slow;
  }
};