您现在的位置是:首页 >技术交流 >代码随想录算法训练营day01_ 704. 二分查找、27. 移除元素网站首页技术交流
代码随想录算法训练营day01_ 704. 二分查找、27. 移除元素
算法性能的评估
时间复杂度和空间复杂度是衡量算法效率的两个重要指标。时间复杂度描述了算法运行所需的时间量,而空间复杂度描述了算法运行时所需的内存空间。
1.时间复杂度
可以用大O符号来表示,例如O(n)表示算法的时间复杂度与输入规模n成正比。以下是一些常见的时间复杂度:
- O(1) 常数时间复杂度:无论输入规模如何,算法的运行时间都是固定的。例如,访问数组中的一个元素。
- O(log n) 对数时间复杂度:算法的运行时间随着输入规模的增加而增加,但增长速度很慢。例如,二分查找算法。
- O(n) 线性时间复杂度:算法的运行时间与输入规模成正比。例如,遍历数组中的所有元素。
- O(n log n) 线性对数时间复杂度:算法的运行时间随着输入规模的增加而增加,但增长速度比线性更快。例如,快速排序算法。
- O(n^2) 平方时间复杂度:算法的运行时间随着输入规模的增加而增加,增长速度很快。例如,嵌套循环遍历二维数组。
2.空间复杂度
也可以用大O符号来表示。例如,O(1)表示算法所需的额外内存量与输入规模无关,O(n)表示算法所需的额外内存量与输入规模成正比。以下是一些常见的空间复杂度:
- O(1) 常数空间复杂度:算法所需的额外内存量固定,与输入规模无关。例如,交换两个变量的值。
- O(n) 线性空间复杂度:算法所需的额外内存量与输入规模成正比。例如,复制一个数组。
- O(n^2) 平方空间复杂度:算法所需的额外内存量与输入规模的平方成正比。例如,创建一个二维数组。
704.二分查找
题目链接
1.使用二分查找的前提是数组升序
2.二分查找的时间复杂度为O(logn),空间复杂度为O(1)
3.二分查找最主要的问题在于区间开闭的选择
区间的选择取决去right的取值,如果right = nums.length - 1
,我们知道数组的最后一个元素下标正好为nums.right - 1
,所以为左闭右闭区间,这个时候再来判断while条件里的<还是<=,我们假设为<,那么循环的结束条件为left == right
,但由于left == right
(举例为[2, 2],)是对于左闭右闭区间是成立的,所以应该为<=符号,<=的结束条件为left == right + 1
;
左闭右闭区间
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] == target) {
return mid;
}
}
return -1;
}
}
同理,当right = nums.length
,nums.length
是取不到的,所以使用<,结束条件为left == right
即可
左闭右开区间
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] == target) {
return mid;
}
}
return -1;
}
}
27. 移除元素
题目链接
1.原地移除指定的元素,只能使用O(1)的空间复杂度
方法一:暴力
思路: 遍历数组,找到需要移除的元素,就把该元素后的所有元素向前移动,来实现覆盖的效果.
时间复杂度:O(n2)
空间复杂度:O(1)
class Solution {
public int removeElement(int[] nums, int val) {
int len = nums.length;
for (int i = 0; i < len; i++) {
// 发现目标元素就将数组整体向前移动一位
if (nums[i] == val) {
for (int j = i + 1; j < len; j++) {
// 用目标元素的后一位元素去覆盖目标元素
nums[j - 1] = nums[j];
}
// i以后的数值都向前移动了一位,所以i也向前移动一位
i--;
// 数组前移后,数组大小减一
len--;
}
}
return len;
}
}
方法二:快慢指针
思路:使用快慢指针,核心思路就是,慢指针找到一个需要移除的元素后就不移动了,等待快指针找到不需要移除的元素,然后进行替换,就实现了原地移除指定元素的效果
时间复杂度:O(n)
空间复杂度O(1)
class Solution {
public int removeElement(int[] nums, int val) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != val) {
nums[slow++] = nums[fast];
}
}
return slow;
}
}