代码随想录算法训练营第一天：数组part01

** 704. 二分查找 **
leetcode链接：https://leetcode.cn/problems/binary-search/
题目描述：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
核心思路：二分法。当数组为有序数组时可以使用。时间复杂度：O(logn) 空间复杂度：O(1)

点击查看代码

```cpp
class Solution {
public:int search(vector<int>& nums, int target) {int left = 0,right = nums.size() - 1;while(left <= right){ //**mistake1：**"="，左闭右闭区间时，应包含=的情况。int mid = left + (right - left) / 2;if(target < nums[mid]){//**mistake2**：使用nums[mid]而不是mid，粗心right = mid - 1;}else if(target > nums[mid]){left = mid + 1;}else{return mid;}}return -1;}
};

</details>
另一种情况，当区间为左闭右开时，right取值为nums.size(),循环条件不在包含=的情况，当nums[mid]与target比较时，当nums[mid]>target时，right = nums[mid];** 27. 移除元素**
leetcode链接：https://leetcode.cn/problems/remove-element/
题目描述：给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
你不需要考虑数组中超出新长度后面的元素。使用方法：暴力法或者双指针法。
暴力法：双循环嵌套，主要注意有效长度size，需理解size和i--的含义，原文并没有讲清楚这一点。
<details>
<summary>点击查看代码</summary>

class Solution {
public:int removeElement(vector<int>& nums, int val) {int size = nums.size();//定义size为数组的有效范围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--后再++确保了在原地进行修改size--;//size--则是将有效范围-1，相当于删去了最后一位，因为最后一位的数值已复制到前一位，随着循环进行，需要删除的数一直往前赋值就可以实现在原地进行修改}}return size;}
};

</details>双指针法：双指针的核心在于如何设计双指针。
<details>
<summary>点击查看代码</summary>

class Solution {
public:int removeElement(vector<int>& nums, int val) {int slowly = 0;for(int fast = 0;fast<nums.size();fast++){if(nums[fast] != val){nums[slowly++] = nums[fast];//核心：当找到目标值时，slowly停止移动，而fast会继续移动到下一位。如果下一位不等于目标值，此时slowly被覆盖后向下继续移动}}return slowly;}
};

</details>
**27. 移除元素**
leetcode链接：https://www.bilibili.com/video/BV12A4y1Z7LP
题目描述：给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
思路：双指针法。同样是如何设计双指针，由于数组非递减，考虑将双指针指向数组两端，指向的数开平方后进行比较，定义一个新数组result来存储比较的结果。
首先使用暴力法，快速排序
<details>
<summary>点击查看代码</summary>

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {for(int i = 0;i < nums.size();i++){nums[i] *= nums[i];}sort(nums.begin(),nums.end());//快排return nums;}
};

</details>双指针法：
<details>
<summary>点击查看代码</summary>

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {vector<int> result(nums.size(),0);int k = nums.size() - 1;for(int i = 0, j = nums.size() - 1;i <= j;){//for( 初始化表达式 ; 条件判断表达式 ; 递增/递减表达式 )if(nums[i]*nums[i] < nums[j]*nums[j]){result[k--] = nums[j]*nums[j];j--;}else{result[k--] = nums[i]*nums[i];i++;}}return result;}
};

</details>

资讯详情

相关新闻