算法训练第一天- 704. 二分查找、27. 移除元素

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

704. 二分查找

自己审题思路

1、有序数组
2、数组不含重复元素

很自然可以想到使用二分查找。

看完代码随想录题解后的收获

1、数组查找中的区间定义非常重要，左闭右开([left, right))和左闭右闭([left、right])决定着代码的边界处理（重要！！！）；
2、为防止大数溢出 (left + right)最好写成如下两种形式：left + (right - left) / 2 || left + ((right - left) >> 1);

左闭右闭代码(详细注释)：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
        while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

左闭右开代码:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int result = -1, left, right, middle;
        left = 0;
        right = nums.size(); // 定义target在左闭右开的区间里，[left, right) 
        while (left < right) { // 当left==right，区间[left, right)无效，所以用 <
            middle = left + ((right - left) >> 1); // 防止溢出，等同于(right + left)/2
            if (target == nums[middle]) return middle;
            else if (target < nums[middle]) {
                right =  middle;
            } else {
                left = middle +  1;
            }
        }
        return result;
    }
};

参考详解

27. 移除元素

自己审题思路

第一时间只想到了暴力解法，两层for循环(一层用来遍历数组，一层用来替换数组里的值)。

暴力解法代码实现(错误实现)

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int sum = 0;
        for(int i = 0;i < nums.size();i++) {
            if (nums[i] == val) {
                sum++;
                for(int j = i + 1; j < nums.size(); j++) {
                    nums[j -1] = nums[j];
                }
            }    
        }
        return nums.size() - sum;
    }
};

上述错误实现在debug的时候发现：
1、发现需要移除的元素，将数组集体向前移动一位之后，因为下标i以后的数值都向前移动了一位，所以i也需要向前移动一位(不然有些元素会遍历不到)；
比如示例nums = [3,3,2,2], val = 3 ------正确处理结果应该为[2,2,2,2]
但是数组变化为[3,2,2,2]就不再变化，究其原因就是代码遍历nums[0]后对数组进行处理变为[3,2,2,2]后，未进行i--，使代码从新的数组第二个元素nums[1]处进行处理，没有删除本应该删除的第二个3。
2、将数组整体前移后，只需要再遍历前面几位即可(相当于将数组后几位截掉)。

暴力解法代码实现(正确实现)

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--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
                size--; // 此时数组的大小-1
            }    
        }
        return size;

    }
};

看完代码随想录题解后的收获

1、使用双指针来实现思路非常清晰，代码简洁；
快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
慢指针：指向更新 新数组下标的位置

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIndex = 0;
        int fastIndex;

        for (fastIndex = 0; fastIndex  < nums.size(); fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }
};

参考详解

今日感想：

万事开头难，加油！