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

admin2024-04-03  0

今日任务

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

  1. 二分查找
    题目链接: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

  2. 移除元素
    题目链接: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;
  }
};
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!