Day1_算法训练营第一天 |704. 二分查找、27. 移除元素

一、提要

        今天第一天学习的是数组的内容,具体算法有关的是二分查找和数组中移除元素,在力扣中的具体题目是704.二分查找27.移除元素,并且有附加题目如下。

二、附加题目

1.二分数组

2.移除元素

#其他语言版本                     

 三、题目完成AC代码

part1:

704.二分数组(分别为左闭右闭和左闭右开)

在这之中卡哥的视频课中十分明确的展示了

//最基础的二分查找代码 左闭右闭
int search(int* nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize- 1;
    int mid = 0;
    while(left <= right){
        mid = (left + right)/2;
        if(target < nums[mid]){
            right = mid - 1;
        }
        if(target > nums[mid]){
            left = mid + 1;
        }
        if(nums[mid] == target){
            return mid;
        }
    }
}
//同样为简单二分 但是解决方式设置的是左闭右开
#include <vector>
using namespace std;

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0 ;
        int right = nums.size() - 1;
        int mid = 0;
        while(left < right){
            mid = (left + right)/2;
            if(nums[mid] > target){
                right = mid;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
};

35.搜索插入位置(opens new window)

1.暴力法暴力并不一定就是慢的,有的时候反而很快

/*给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

 

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4
*/
#include<bits/stdc++.h>
using namespace std;

int search(vector<int>& nums,int target){
    for(int i = 0; i < nums.size(); i++){
        if(nums[i] >= target){
            return i;
        }
    }
    return nums.size();
}

2.二分法思路比较简单

/*给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

 

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4
*/
#include<bits/stdc++.h>
using namespace std;

int searchInsert(int* nums, int numsSize, int target) {
    int lf = 0, ri = numsSize - 1;
    while(lf < ri){
        int mid = (lf + ri)/2;
        if(nums[mid] < target){
            lf = mid + 1;
        }
        if(nums[mid] > target){
            ri = mid - 1;
        }
        if(nums[mid] == target){
            return mid;
        }
    }
    if(lf == numsSize - 1){
        return numsSize - 1;
    }
    else{
        return lf;
    }
}

34.在排序数组中查找元素的第一个和最后一个位置(opens new window)

1.暴力

/*
给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

 

示例 1:

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
示例 2:

输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
示例 3:

输入:nums = [], target = 0
输出:[-1,-1]
*/

//无脑暴力解法  内存小速度快
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target){
    int end = 0,strat = -1;
    for(int i = 0; i < nums.size() ;i++){
        if(nums[i] == target && strat == -1){
            strat = i;
        }
        if(nums[i] == target){
            end = i;
        }
    }
    vector<int> returnSize;
    returnSize[0] = strat;
    returnSize[1] = end;
    return returnSize;
    }
};

2.二分法

/*给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

 

示例 1:

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
示例 2:

输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
示例 3:

输入:nums = [], target = 0
输出:[-1,-1]
*/

//二分法解决方法
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    int shLeftBorder(vector<int>& nums, int target){
        int le = 0, ri = nums.size() - 1, leftBorder = -2;
        while(le <= ri){
            int mid = (le + ri)/2;
            if(nums[mid] < target){
                le = mid + 1;
            }else{
                ri = mid - 1;
                leftBorder = ri;
            }
        }
        return leftBorder;
    }
    
    int shRightBorder(vector<int>& nums, int target){
        int le = 0,  ri = nums.size() - 1, rightBord = -2;
        while(le <= ri){
            int mid = (le + ri)/2;
            if(nums[mid] <= target){
                le = mid + 1;
                rightBord = le;
            }else{
                ri = mid - 1;
            }
        }
        return rightBord;
    } 

    vector<int> searchRange(vector<int>& nums, int target){
        int leB = shLeftBorder(nums,target) ;
        int riB = shRightBorder(nums,target) ;
        vector<int> x(2,0);
        if(leB == -2 || riB == -2) return {-1,-1} ;
        if(riB - leB > 1) return {leB + 1,riB - 1};
        return {-1-1};
    }
};

69.x 的平方根(opens new window)

这里面int可以换为longlong

/*给你一个非负整数 x ,计算并返回 x 的 算术平方根 。

由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。

注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。

 

示例 1:

输入:x = 4
输出:2
示例 2:

输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
*/

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    int mySqrt(int x) {
        int left = 0;
        int right = x - 1;
        while(left <= right){
            int mid = (left + right)/2;
            if(mid*mid < x){
                left = mid + 1;
            }else if(mid*mid > x){
                right = mid - 1;
            }else if(mid*mid == x){
                return mid;
            }
        }
        return left - 1;
    }
};

part2:

27.移除元素

/*
27. 移除元素
提示
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

 

说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说,不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
 

示例 1:

输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2]
解释:函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为 2 ,而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。
示例 2:

输入:nums = [0,1,2,2,3,0,4,2], val = 2
输出:5, nums = [0,1,3,0,4]
解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
 

提示:

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
*/

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0;
        for(int fast = 0; fast < nums.size(); fast++){
            if(nums[fast] != val){
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
}; 

26.删除排序数组中的重复项(opens new window)

/*
26. 删除有序数组中的重复项
提示
给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过:

更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。
判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}
如果所有断言都通过,那么您的题解将被 通过。

 

示例 1:

输入:nums = [1,1,2]
输出:2, nums = [1,2,_]
解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2:

输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]
解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
 

提示:

1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 非严格递增 排列
*/
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int slow = 0;
        int val = nums[0];
        for(int fast = 0; fast < nums.size() ; fast++){
            if(nums[fast] != val){
                nums[++slow] = nums[fast];
                val = nums[fast];
            }
        }
        return slow + 1;
    }
};

四、总结心得

二分查找法:①while中条件的判断取决于你想选取的有效区间是 "[ )" 还是 "[ ]"        ②更新时是否加减一也取决于边界的选取       

移除元素:使用双指针的思路!遍历(两个循环到一个)实现O(n) 

加:做题中可以记忆一些位运算使代码运行速度得到提升不过慎用,毕竟可读性实属一般,并且问题解决时要注意分块解决!由子问题到主问题!                LC26,在这个题目中,我的感悟是不要局限于算法刚开始的模板,比如双指针比如二分,要有适用题目的思考更重要的是思想的学习!理解思想才是根本!要去运用已知的工具不要被工具限制!!!

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-21 21:22:01       143 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-21 21:22:01       157 阅读
  3. 在Django里面运行非项目文件

    2024-07-21 21:22:01       132 阅读
  4. Python语言-面向对象

    2024-07-21 21:22:01       142 阅读

热门阅读

  1. C++ STL partion_point用法

    2024-07-21 21:22:01       25 阅读
  2. 【深度学习】sdxl的Lora训练技巧

    2024-07-21 21:22:01       32 阅读
  3. 理解Cookie、Session和Token

    2024-07-21 21:22:01       28 阅读
  4. 第四节shell条件测试(5)

    2024-07-21 21:22:01       34 阅读
  5. Python内存泄漏排查

    2024-07-21 21:22:01       26 阅读
  6. 【瓴岳科技】历史面试题

    2024-07-21 21:22:01       31 阅读
  7. 揭秘Odoo OWL的魔法:reactive vs useState

    2024-07-21 21:22:01       25 阅读