NO.1 | 704. 二分查找，27. 移除元素

题目链接：704.二分查找

• 前置条件：数组是有序的才可以，如果是乱序的数组则不可使用该题方法
• 暴力解法：直接遍历，对每个元素都进行判断是否等于target，时间复杂度O(n)。但是这样就没有使用上数组有序的这个条件
• 二分查找： 代码及注释如下

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 有序数组 --> 二分查找
        // left为数组的起始位置， right为数组的末尾位置
        int left = 0;
        int right =  nums.size()-1;
        int mid = 0;
        while(left <= right)
        {   
            // 更新mid
            // 以下写法优于 mid = (left + right) / 2
            mid = left + (right - left) / 2;
            if(nums[mid] < target)
            {
                // 由于数组是升序，此时说明target在当前所以mid的右边
                // left=mid相当于把mid左边的排除掉
                left = mid + 1;
            }
            else if(nums[mid] > target)
            {   
                right = mid - 1;
            }
            else
            {
            	// nums[mid] == target
                return mid;
            }
        }
        // 如果nums中不存在target,则返回-1
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

题目链接：27. 移除元素
解题思路：用覆盖代替删除，舍弃val的元素，然后被其他元素覆盖

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        // 有效的元素
        int valid_pos = 0;
        // 遍历数组
        for(int i = 0; i < nums.size(); i++)
        {
            // val != nums[i]，说明 i 不需要被覆盖，就放到有效位上
            if(val != nums[i])
            {
                // 实现后面的元素前移，而且不用特意删除前面的元素，直接覆盖掉
                nums[valid_pos] = nums[i];
                valid_pos += 1;
            }
            else
            {
                // val == nums[i]
                // 不对 i 处理，如果要用到该位置，也会被覆盖掉
            }
        }
        return valid_pos;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

双指针思路讲解：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html#%E6%80%9D%E8%B7%AF