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

数组理论基础

文档讲解：数组理论基础
视频讲解：暂无
状态：😀

数组要点

  • 数组是存放在连续内存空间的相同类型数据的集合。
  • 数组的下标都是从0开始的。
  • 数组内存空间的地址是连续的。
  • 数组中的元素不能删除，只能进行覆盖。

所以增删元素的时候需要对其他元素的地址做相关操作。

C++相关

  • 在C++中，vector和array存在区别，vector的底层实现是array，严格来说vector是容器，不是数组。
  • 在C++中，二维数组在内存空间上是连续分布的。

704.二分查找

题目链接：704. 二分查找
文档讲解：704. 二分查找
视频讲解：二分查找法
目标：熟悉根据 左闭右开，左闭右闭 两种区间规则 学出来的二分法
状态：以前的方法全都忘记了，边界条件含糊不清，还是要多总结

学习前的想法

因为平常也了解过一些简单的算法，加上学校上课提到的，二分查找的基本思想我是了解的，只需不断的将区间的中位数与目标值作比较，选择左右区间，直到找到目标值或数组越界。

尝试写出代码如下（错误）： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int length = nums.size() - 1;

        while (length < nums.size() && length > -1) {
            if (nums[length] == target)
                return length;

            if (nums[length] > target) {
                length--;
                length -= length / 1;
            }

            if (nums[length] < target) {
                length++;
                length += (nums.size() - 1 - length) / 1;
            }
        }

        return -1;
    }
};

代码超时！

反思之后，在写题时对边界条件没有很好的理解，导致浪费了大量时间还没写对。

2024/2/21
个人并没有看出代码是在哪里出错，可能是循环终止条件有问题。🥲

学习后的想法

二分法的关键是处理好边界问题，包括：循环边界，区间边界

一般来说，我们采用的有两种边界取法，左闭右闭，左闭右开，以left和right分别表示数组的边界，即[left, right]和[left, right)。

在二分法中，有两处需要判断边界，一处为while循环的终止条件，另一处为选择边界时left或者right与middle的取值。

我们在解决这类问题时，需要选择上述所说的一种区间，然后一路走到底。对于每处边界判断，都要以我们所选定的区间来取舍，来判断进行选择后取值是否符合区间范围。

卡哥讲的很清楚，确实是让我理解了这个边界选择的方法，以前看acwing的视频没有理解为什么，只背了模板，结果时间长了模板忘了，题也做不对了。

实现

左闭右闭 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 区间左闭右闭，[left, right]
left = 0;
right = nums.size() - 1;

// left==right时，区间[left, right]依然有效，所以用<=
while(left <= right) {
	// 使用 middle = left + ((right - left) / 2)可以防止溢出
	middle = (left + right) / 2;
	
	if(nums[middle] > target) right = middle - 1; // 左区间，[left, middle - 1]
	else if(nums[middle] < target) left = middle + 1; // 右区间，[middle + 1, right]
	else return middle;// 找到目标值，将其返回
}

// 未找到目标值
return -1;

左闭右开 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 区间左闭右闭，[left, right)
left = 0;
right = nums.size();

// left==right时，在区间[left, right)无效，所以用<
while(left < right) {
	// 使用 middle = left + ((right - left) / 2)可以防止溢出
	middle = (left + right) / 2;
	
	
	if(nums[middle] > target) right = middle; // 左区间，[left, middle)
	else if(nums[middle] < target) left = middle + 1; // 右区间，[middle + 1, right)
	else return middle; // 找到目标值，将其返回
}

// 未找到目标值
return -1;

27.移除元素

题目链接：27.移除元素
文档讲解：27. 移除元素
视频讲解： LeetCode：27. 移除元素
状态：暴力法能够解决，不过还是不熟练，双指针法确实开拓了思路

学习前的想法

题目给出了一个数组中nums和一个值val，要求原地移除所有数值等于val的元素，并返回移除后数组的新长度。

原地算法，即空间复杂度为O(1)

暴力法（双层for循环）：我的想法是遍历数组，遇到与val相等的值，则将后续所有元素向前移动一位，接着从当前位置继续遍历，并将数组长度减一。

代码实现： 

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
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int length = nums.size();

        if(length == 0) {
            return 0;
        } else {
            for(int i = 0; i < length; i++) {
                if(nums[i] == val) {
                    for(int j = i; j < nums.size() - 1; j++) {
                        nums[j] = nums[j + 1];
                    }

                    length--;
                    i--;
                }
            }
        }

        return length;
    }
};

2024/2/21
和卡哥的代码对比，for循环前对length==0的判断似乎没有必要

学习后的想法

题外话：有关库函数的使用问题
卡哥的建议：如果一道题目使用库函数可以直接解决，不建议使用；如果使用库函数知识解决这个问题的其中一小步，并且我们直到这个库函数内部的实现过程，以及它的时间复杂度，可以用。

1
2
3
4
vector.erase()
作用：删除元素
原理：将后面元素向前移，将删除元素覆盖
时间复杂度:O(n)

使用双指针法可以达到O(n)的时间复杂度，仅使用一层for循环：

快指针：声明为fast，初始值为0，用于遍历数组，找到所有不等于目标元素，应该保留的值。

慢指针：声明为slow，初始值为0，相当于指向一个空的、新的数组，不断的填入快指针找到的值。

流程：
当快指针指向的值符合条件时，即不等于val时，将该值赋给慢指针指向的位置，fast++; slow++;
当快指针指向的值不符合条件，即等于val时，跳过该元素不赋值，fast++; slow不变;
最终，当快指针遍历完数组时，慢指针指向其所表示新数组的最后一个元素的后一位，由于其值从0开始，因此慢指针的位置便是新数组的长度。

实现过程记录

1
2
3
4
5
6
7
8
9
10
11
12
// 时间复杂度：O(n)
// 空间复杂度：O(1)
int slow = 0;

// 快指针遍历数组（一个for循环）
for(int fast = 0; fast < nums.size(); fast++) {
	if(nums[fast] != val) {
		nums[slow++] = nums[fast];
	}
}

return slow;

收获与学习时长

学习时长：3h45min

收获

熟悉了 根据 左闭右开，左闭右闭 两种区间规则 写出来的二分法。

掌握双指针法解决移除元素。（相向双指针暂时没有手敲，思路时使用左右指针进行遍历）