代码随想录算法训练营第一天 | 704. 二分查找 、27. 移除元素

704.二分查找

1.Thought:

循环遍历数组元素，找到目标记录并返回下标i，若未找到，则返回-1.（注意应用有序、无重复）

2.实践：

2.1左闭右闭：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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;
            if (nums[mid] == target) {
                return mid;
            }
            else if (nums[mid] < target) {
                left = mid + 1;
            }
            else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        return -1;
    }
};

2.2左闭右开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
            if (nums[mid] < target) {
                left = mid + 1;
            }
            else if (nums[mid] > target) {
                right = mid;
            }
            else
                return mid;
        }
        return -1;
    }
};

3.总结：

3.1 :

有序不重复数组应想到二分法

3.2 :

二分法包含左闭右闭与左闭右开，注意循环结束判断条件，以及右端点的选取

27、移除元素

1.Thought:

遍历整个数组，遇到目标元素将其用后一个不等于他的元素顶替。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int len = nums.size();
        for (int i = 0; i < nums.size(); i++) {
            int j = i;
            if (nums[j] == val) {
                while (nums[j + 1] == val) {
                    j++;
                }
                nums[i] = nums[j + 1];
                len--;
            }
            i++;
        }
        return len;
    }
};

修改后：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int len = nums.size();
        int i = 0;

        while (i < len) {
            if (nums[i] == val) {
                nums[i] = nums[len - 1];
                len--;
            } else {
                i++;
            }
        }
        return len;
    }
};

在这个方法中，当发现当前元素等于 val 时，将最后一个元素复制到当前位置，同时减小数组长度。由于我们将最后一个元素复制到当前位置，所以不需要担心数组的顺序问题。（即将目标元素移到最后）

2.双指针法：

思路：使用两个指针，第一个用来遍历数组，第二个用于生成目标数组。如果遍历到非目标值，则继续，否则将非目标值加到生成数组中，其指针向后加一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int len = nums.size();
        int n=0;
        for (int i = 0; i < len; i++) {
            if (nums[i] != val) {
                nums[n] = nums[i];
                n++;
            }
        }
        return n;
    }
};