day01 二分查找 移除元素

题目1：704二分查找

题目链接：704 二分查找

题意

找到升序的整数数组nums中与target相等的数字，并返回下标，如果没有则返回-1

二分法前提：有序数组，无重复元素

区间左闭右闭   [left，right]

意味着可以取到right，即可以取到区间最右侧的值

定义right元素的时候，注意right=nums.size()-1  可以取到

代码

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

• 时间复杂度：O(log n)
• 空间复杂度：O(1）

区间左闭右开  [left，right]

意味着不可以取到right，即不可以取到区间最右侧的值

定义right的时候，注意right=num.size()   取不到

代码

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

• 时间复杂度：O(log n)
• 空间复杂度：O(1）

扩展题目a：35搜索插入位置

题目链接：35 搜索插入位置

题意

nums数组升序排列（无重复元素），返回数组中与target相等的元素的位置，若没有，则返回target在数组中应该插入的位置

插入的位置会有如下4种情况：

• 目标值在数组所有元素之前   
• 目标值等于数组中某一个元素  return mid
• 目标值插入数组中的位置    
• 目标值在数组所有元素之后  

左闭右闭

代码

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        //左闭右闭
        int left = 0;
        int right = nums.size() - 1;
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(nums[mid] < target){
                left = mid + 1;
            }
            else if(nums[mid] > target){
                right = mid - 1;
            }
            else {
                return mid;
            }
        }
        // return left;
        return right + 1 ;
        //不可以返回mid,mid是一个局部变量，只在while循环里面有用
    }
};

注意最终return的不可以是mid，因为mid是一个局部变量，只在while循环里面有效

• 时间复杂度：O(log n)
• 空间复杂度：O(1)

左闭右开

代码

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        //左闭右开
        int left = 0;
        int right = nums.size();
        while(left < right){
            int mid = left + ((right - left) >> 1);
            if(nums[mid] < target){
                left = mid + 1;
            }
            else if(nums[mid] > target){
                right = mid;
            }
            else {
                return mid;
            }
        }
        // return left;
        return right;  //与左闭右闭不同的是，左闭右开取不到右边界值，所以数字会插入在这个位置的
    }
};

• 时间复杂度：O(log n)
• 空间复杂度：O(1)

暴力解法（较高的时间复杂度）

循环遍历整个数组，比较数组的每个元素与target的大小关系

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
      //暴力解法
      for(int i = 0;i<nums.size();i++){
          if(nums[i] >= target){
              return i;
          } 
      }
      return nums.size();
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1）

扩展题目b：在排序中查找元素的第一个位置

题目链接：34 在排序数组中查找元素的第一个和最后一个位置

题意

找出非递减排列的整数数组nums中  与target相等的元素的开始位置和结束位置

如果不存在与target相等的元素，返回[-1，-1]

寻找target在数组里的左右边界，有如下三种情况：

• 情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}
• 情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
• 情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}

代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int rightboard = getrightboard(nums, target);
        int leftboard = getleftboard(nums, target);
        if(rightboard == -2 || leftboard == -2){
            return {-1,-1};
        }
        if(rightboard - leftboard > 1){
            return {leftboard + 1, rightboard - 1};
        }
        return {-1, -1};

    }
private:
    int getrightboard(vector<int>& nums, int target){
        int left = 0;
        int right = nums.size() - 1;
        int rightboard = -2;
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(nums[mid]>target){
                right = mid - 1;
            }
            else{
                left = mid + 1;
                rightboard = left;
            }
        }
        return rightboard;
    }

    int getleftboard(vector<int>& nums, int target){
        int left = 0;
        int right = nums.size() - 1;
        int leftboard = -2;
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(nums[mid] >= target){
                right = mid - 1;
                leftboard = right;
            }
            else{
                left = mid + 1;
            }
        }
        return leftboard;
    }
};

题目2：27移除元素

题目链接：27 移除元素

题意

原地移除数组中所有数值等于val的元素，返回新的数组长度

暴力解法（两层for循环）

一层是循环遍历数组的每个元素，另一层是比较更新数组

代码

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--;//在nums[i]==val的情况下，元素都向前移了一位
               size--;//因为元素向前移动一位，所以长度减1
           }
       }
       return size;
    }
};

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

双指针★

fast快指针 nums[fast]与val比较   寻找新数组里面的元素（!=val）

slow新数组的下标

代码

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0;
        for(int fast = 0;fast < nums.size();fast++){
            if(nums[fast] != val){
                nums[slow] = nums[fast];
                slow ++;
            }
        }
        return slow;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)