Day01数组
一、数组注意事项
三点需要注意：
数组是存放在连续内存空间上的相同类型数据的集合。数组下标都是从0开始的。数组内存空间的地址是连续的。因为数组的在内存空间的地址是连续的，所以在删除或者增添元素的时候，就难免要移动其他元素的地址。
二、力扣相关例题
今日数组解题 → 暴力解法、二分查找、双指针法
LeetCode704. 二分查找
题目： 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 示例 : 输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4
class Solution {
public:
int search(vector
int left = 0;
int right = nums.size()-1;
int middle; //middle中间值
while (left <= right) {
middle = (left + right) / 2; //准确这里应该用(left+(right-left)/2) 目的是防止溢出
if (nums[middle] > target) { //target位于左区间
right = middle - 1;
}else if (nums[middle] < target) { //target位于右区间
left = middle + 1;
}else { //nums[middle] == target
return middle;
}
}
return -1;
}
};
感悟：二分查找最基本的例题之一，重点注意区间取值，左闭右闭、左闭右开等所对应的left、right、middle的取值
LeetCode27. 移除元素
给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于val的元素，并返回移除后数组的新长度。 示例 ： 输入：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]，也会被视作正确答案。
//暴力解法
class Solution {
public:
int removeElement(vector
int len = nums.size();
for (int i=0; i if (nums[i] == val) { for (int j=i+1; j nums[j-1] = nums[j]; //覆盖前一个元素的值 } i--; len--; //覆盖完数组总长度减一 } } return len; } }; //双指针法 class Solution { public: int removeElement(vector int slow = 0; //慢指针，指向更新新数组下标的位置 for (int fast = 0; fast < nums.size(); fast++) { //快指针，寻找新数组的元素 ，新数组就是不含有目标元素的数组 if (nums[fast] != val) { //若不等，则后面覆盖前面 nums[slow++] = nums[fast]; //nums[slow] = nums[fast] //slow++ } } return slow; } }; 感悟：①暴力解法，两层for循环，时间复杂度为O(n^2)；②双指针法，也叫快慢指针法， 通过快指针和慢指针在一个for循环下完成两个for循环的工作，特别注意快慢指针所对应的含义，时间复杂度O(n) LeetCode35. 搜索插入位置 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 示例 : 输入: nums = [1,3,5,6], target = 5 输出: 2 //二分法 //这道题有四种情况 //1.目标值在数组所有元素之前 [2,4,6] 1 //2.目标值等于数组中某一个元素 [2,4,6] 4 //3.目标值插入数组中的位置 [2,4,6] 5 //4.目标值在数组所有元素之后 [2,4,6] 7 class Solution { public: int searchInsert(vector int left = 0; int right = nums.size() - 1; //特别需要注意right的数值，很容易携程right = nums.size() int middle; while(left <= right) { middle = left + ((right - left) >> 1); //右移操作一般会比整数除法效率高 if(nums[middle] > target ) { right = middle - 1; }else if (nums[middle] < target) { left = middle + 1; }else if (nums[middle] == target) { return middle; } } return right + 1; //不能是middle+1，否则目标值在数组所有元素之前通过不了，这边我没想到位卡了有一段时间 } }; 感悟：这道题在704二分查找基础上进阶了点，所考虑的问题情况变多了，在返回值一不小心很容易卡住 LeetCode34. 在排序数组中查找元素的第一个和最后一个位置 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target，返回 [-1, -1]。 示例 ： 输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4] //左右区间的查找是这道题的关键！ //解题思路 → Carl class Solution { public: vector int leftBorder = getLeftBorder(nums, target); //左边界 int rightBorder = getRightBorder(nums, target); //右边界 //target 在数组范围的右边或者左边 if (leftBorder == -2 || rightBorder == -2) return {-1, -1}; //target 在数组范围中，且数组中存在target if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1}; //target 在数组范围中，且数组中不存在target return {-1, -1}; } private: //构造获取右边界函数 int getRightBorder(vector int left = 0; int right = nums.size() - 1; int rightBorder = -2; while(left <= right) { int middle = left + ((right - left) / 2); if (nums[middle] > target) { right = middle - 1; }else { //这边特别得注意相等的情况，若有多个target，则最后下标是最后与target相等的元素下标＋1 left = middle + 1; rightBorder = left; } } return rightBorder; } //构造获取左边界函数 int getLeftBorder(vector int left = 0; int right = nums.size() - 1; int leftBorder = -2; while (left <= right) { int middle = left + ((right - left) / 2); if (nums[middle] >= target) { //这边特别得注意相等的情况，若有多个target，则最后下标是最后与target相等的元素下标-1 right = middle - 1; leftBorder = right; }else { left = middle + 1; } } return leftBorder; } }; 感悟：这道题在今日题目中算是最难的，二分查找的继续进阶，难在左右区间确定，跟前面查找搜索特定元素位置有点不同；由于自身水平不太够，solution内自建函数还不够熟练，看了卡尔学长的解题思路，一步一步理解 继续加油！继续努力！ 欢迎大家指正！ 相关阅读
您阅读本篇文章共花了：
发表评论