1、数组定义:数组是存放在连续内存空间上的相同类型数据的集合。
特点:
2、数组的元素是不能删的,只能覆盖。
1、题目链接:. - 力扣(LeetCode)
2、文章讲解:代码随想录
3、视频讲解:手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode:704. 二分查找_哔哩哔哩_bilibili
4、前提条件:数组为有序数组,数组中无重复元素
5、难点:对区间定义没有想清楚
6、遵循点:循环不变量原则,要不左闭右闭要不左闭右开
class Solution {
public int search(int[] nums, int target) {
// 左闭右闭写法
int left = 0;
int right = nums.length - 1;
while (left <= right) {
// 计算中间索引
// int middle = (left + right) / 2;
// 防止溢出
int middle = left + (right - left) / 2;
if (nums[middle] < target) {
// 左区间
left = middle + 1;
} else if (nums[middle] > target) {
// 右区间
right = middle - 1;
} else {
// 找到了
return middle;
}
}
// 没找到
return -1;
}
}
class Solution {
public int search(int[] nums, int target) {
// 左闭右开写法
int left = 0;
int right = nums.length;
while (left < right) {
// 计算中间索引
// int middle = (left + right) / 2;
// 防止溢出
int middle = left + (right - left) / 2;
if (nums[middle] < target) {
// 左区间
left = middle + 1;
} else if (nums[middle] > target) {
// 右区间
right = middle;
} else {
// 找到了
return middle;
}
}
// 没找到
return -1;
}
}
1、题目链接:. - 力扣(LeetCode)
2、文章讲解:代码随想录
3、视频讲解:数组中移除元素并不容易! | LeetCode:27. 移除元素_哔哩哔哩_bilibili
4、前提条件:不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并原地修改输入数组,元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
5、注意点:数组的元素在内存地址中是连续的,不能单独删除数组中的某个元素,只能覆盖。
class Solution {
// 暴力解法
public int removeElement(int[] nums, int val) {
int size = nums.length;
// 1.先遍历数组
for (int i = 0; i < nums.length; i++) {
// 2.找到要删除的元素
if (nums[i] == val) {
// 3.将后面元素依次前移
for (int j = i + 1; j < nums.length; j++) {
nums[j - 1] = nums[j];
}
i--;
size--;
}
}
// 4.返回数组的长度
return size;
}
}
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];
slow++;
}
}
return slow;
}
}