代码随想录算法训练营第一天 | LeetCode 704(二分查找) LeetCode 35(搜索插入位置) LeetCode 34(在排序数组中查找元素的第一个和最后一个位置 ) LeetCode 27(移除元素)
数组理论基础
数组是存放在连续内存空间上的相同类型数据的集合
要点：
- 数组下标都是从0开始的
- 数组内存空间的地址是连续的 所以在增删操作的时候，就要去移动其他元素的地址
- 数组元素是不能删除的，只能覆盖
- 二维数组在内存的空间地址可能是连续的也可能是不连续的，这取决于编程语言的内存管理；C++中是连续的，Java中是不连续的
704：二分查找
数组有序 查找唯一值下标 时间复杂度O(log n)
类似双指针 设置left&right两个指针开始指向数组开头和结束位置，因为数组有序，且元素唯一，那么我们就可以取left&right的中间值所对应的数组元素和target值比较，若大于target，则更新right；若小于target，则更新left。
那么问题来了！
1.是while(left < right)还是while(left <= right)
2.是right = middle呢，还是要right = middle - 1
解决方法： 边界条件更新时遵循循环不变量原则
解题代码：
方法一：左闭右开 [left,right)
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length;
int middle;
//左闭右开 [left,right) left == right时无意义
while(left < right){
middle = left + ((right - left) >> 1);
if(nums[middle] == target){
return middle;
}else if(nums[middle] > target){
//此时 target值 在[left,middle)中 所以将right赋值为middle
right = middle;
}else {
//此时 target值 在[middle + 1,right)中 所以将left赋值为middle + 1
left = middle + 1;
}
}
return -1;
}
}
方法二： 左闭右闭
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int middle;
//左闭右闭 [left,right] left == right时仍有意义
while(left <= right){
middle = left + ((right - left) >> 1);
if(nums[middle] == target){
return middle;
}else if(nums[middle] > target){
//此时 target值 在[left,middle-1]中 所以将right赋值为middle - 1
right = middle -1;
}else {
//此时 target值 在[middle + 1,right]中 所以将left赋值为middle +1
left = middle + 1;
}
}
return -1;
}
}
总结
关注nums[middle]在下一个区间会不会和target值比较
35：搜索插入位置
这道题相当于在数组中插入目标值，分下述四种情况
1.目标值在数组所有元素之前
2.目标值等于数组中某个元素
3.目标值在数组某两个元素之间
4.目标值在数组元素之后
暴力法
class Solution {
public int searchInsert(int[] nums, int target) {
for(int i = 0; i < nums.length; ++i){
if(nums[i] >= target){
return i;
}
}
return nums.length;
}
}
二分法 左闭右开
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length;
int middle = 0;
while(left < right) {
middle = left + ((right - left) >> 1);
if(target < nums[middle]) {
right = middle;
}else if(target > nums[middle]) {
left = middle + 1;
}else{
return middle;
}
}
// 目标值在数组所有元素之前
// 目标值插入数组中的位置 [left, right) ，return right 即可
// 目标值在数组所有元素之后的情况 [left, right)，因为是右开区间，所以 return right
return right;
}
}
34：在排序数组中查找元素的第一个和最后一个位置
LeetCode 34(在排序数组中查找元素的第一个和最后一个位置)
思路：
方法一：
先用二分找到任意一个目标值 找不到则返回[-1,-1]
找到了 则以该目标值为起点向前后探查边界方法二：
使用两次二分法 查找左右边界
方法一：
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = 0;
int right = nums.length;
int middle;
int begin = -1;
int end = -1;
while(left < right){
middle = left + ((right - left) >> 1);
if(nums[middle] > target){
right = middle;
}else if(nums[middle] < target){
left = middle + 1;
}else {
//找到target值 向两侧遍历查找目标值
begin = middle;
end = middle;
while(begin - 1 >= 0 &&nums[begin-1] == target){
begin--;
}
while(end + 1 < nums.length && nums[end + 1 ] == target){
end++;
}
return new int[]{begin,end};
}
}
return new int[]{begin,end};
}
}
方法二
class Solution {
int[] searchRange(int[] nums, int target) {
int leftBorder = getLeftBorder(nums, target);
int rightBorder = getRightBorder(nums, target);
// 情况一 target 在数组范围的右边或者左边
if (leftBorder == -2 || rightBorder == -2) return new int[]{-1, -1};
// 情况三 target 在数组范围中，且数组中存在target
if (rightBorder - leftBorder > 1) return new int[]{leftBorder + 1, rightBorder - 1};
// 情况二 target 在数组范围中，且数组中不存在target
return new int[]{-1, -1};
}
int getRightBorder(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
// 记录一下rightBorder没有被赋值的情况
int rightBorder = -2;
while (left <= right) {
int middle = left + ((right - left) / 2);
if (nums[middle] > target) {
right = middle - 1;
} else {
// 寻找右边界，nums[middle] == target的时候更新left
left = middle + 1;
rightBorder = left;
}
}
return rightBorder;
}
int getLeftBorder(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
// 记录一下leftBorder没有被赋值的情况
int leftBorder = -2;
while (left <= right) {
int middle = left + ((right - left) / 2);
if (nums[middle] >= target) {
// 寻找左边界，nums[middle] == target的时候更新right
right = middle - 1;
leftBorder = right;
} else {
left = middle + 1;
}
}
return leftBorder;
}
}
27：移除元素
LeetCode 27(移除元素)
要点：数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。
思路：
方法一：直接暴力 双重循环 一个for遍历数组 一个for更新数组
方法二：快慢指针
相向指针
方法一
class Solution {
public int removeElement(int[] nums, int val) {
int size = nums.length;
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--;
//此时数组的大小-1
size--;
}
}
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];
}
}
return slow;
}
}
//相向双指针
class Solution {
public int removeElement(int[] nums, int val) {
//定义双向指针
int left = 0;
int right = nums.length - 1;
//找到右侧第一个不为val值的索引
while(right >= 0 && nums[right] == val){
right--;
}
while(left <= right){
//判断nums[left]是否为val
if(nums[left] == val){
nums[left] = nums[right];
right--;
}
left++;
//再去寻找右侧第一个不为val值的索引
while(right >= 0 && nums[right] == val){
right--;
}
}
return left;
}
}