跳转至

704.二分查找 & 27.移除元素

约 241 个字 50 行代码 预计阅读时间 1 分钟

Luck

荣幸在B站24.01-24抽奖中了Carl哥的算法训练营！(😆) → 参考网站

陆陆续续学过一些算法，争取坚持系统学一遍！

704.二分查找

第一想法：暴力求呗，因为是升序的，直接循环找即可 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int search(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i ++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return -1;
    } 
};
但题目是 二分查找 呀！而且数组有序，定考虑二分 (区间要注意!) 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1; // index 

        while(l <= r) {
            int mid = l + ((r - l) >> 1); // 防溢出

            if (nums[mid] > target) r = mid - 1;
            else if (nums[mid] < target) l = mid + 1;
            else return mid;
        }
        return -1;
    }
};

27.移除元素

原地移除等于val的元素 & 空间要求\(O(1)\)，最终返回新的数组长度

原地如何移除？数组元素能删除？ → NO，本质即 覆盖 呗!

  1. 想法: 暴力 → 循环找到目标val，循环后一个先前进行覆盖 

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
    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 --;
                size --;
            }
        }
        return size; 
    }
};

  2. 快慢指针 → ref, 动图参考

    • 对暴力进行优化，利用双指针降低复杂度（即一层循环\(O(n)\)

快指针来索引新数组需要的元素，更新到慢指针索引上，最终返回慢指针即可（太强了!!! 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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];
        }
        return slow;
    }
};

颜色主题调整

快来和我聊天~

可以的话请给我赞和 star喔~    =>  GitHub stars

评论