JLUVicent

704二分查找&27移除元素

 
  • 2023年 02月15日
  • 0 阅读

704二分查找&27移除元素

LeetCode 704 二分查找

题目链接：704.二分查找

二分法简单，细节是魔鬼，这个我是看了卡哥的视频，目前已经熟悉 根据 左闭右开，左闭右闭 两种区间规则 写出来的二分法

image-20230215081153090

注意两者的异同点。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // int left = 0;
        // int right = nums.size() - 1;
        // // 左闭右闭的写法 左闭右开在下面right赋值不需要减一
        // while ( left <= right ){
        //     // c++定义基础不牢固，定义变量要加上变量类型
        //     int middle = left + ( right - left ) / 2; //防止溢出
        //     if ( nums[middle] > target ){
        //         right = middle -1;
        //     }
        //     else if ( nums[middle] < target ){
        //         left = middle + 1;
        //     }
        //     else{
        //         return middle;
        //     }
        // }
        // return -1;
        
        // 左闭右开写法
        int left = 0;
        int right = nums.size();
        // 左闭右闭的写法 左闭右开在下面right赋值不需要减一
        while ( left < right ){
            // c++定义基础不牢固，定义变量要加上变量类型
            int middle = left + ( right - left ) / 2; //防止溢出
            if ( nums[middle] > target ){
                right = middle;
            }
            else if ( nums[middle] < target ){
                left = middle + 1;
            }
            else{
                return middle;
            }
        }
        return -1;

    }
};
  • 时间复杂度：O(log n )，其中 n是数组的长度。
  • 空间复杂度：O(1)

LeetCode 27 移除元素

题目链接：27.移除元素

思路：这个题就相当于让实现库函数erase。

讲解视频

image-20230215085101986

暴力解法和双指针解法两种

暴力解法使用两层for ,第一层遍历整个数组，第二层用来更新覆盖数组 O(n^2) O(1)

双指针法定义两个指针，fast指针用来遍历数组找到target，slow指针用来更新数组中的元素从而实现覆盖 O(n) O(1)

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 += 1;
            }
        }
        return slow;
        
        // // 暴力解法
        // 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--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
        //         size--; // 此时数组的大小-1
        //     }
        // }
        // return size;
        
        //暴力中的i--是因为覆盖后下标i以后的数值都向前移动了一位，如果i不向前移动，就会导致无法删除两个相邻的val eg:[1,2,2,3,4] 2

    }
};
// 其次要注意本题的返回值
搜索