网站开发中 即将上线,广州天河区做网站,广告效果图用什么软件做,免费客户销售管理软件数组基础
1、数组定义#xff1a;数组是存放在连续内存空间上的相同类型数据的集合。
特点#xff1a;
数组下标都是从0开始的。数组内存空间的地址是连续的
2、数组的元素是不能删的#xff0c;只能覆盖。
704. 二分查找
1、题目链接#xff1a;. - 力扣#xff08…数组基础
1、数组定义数组是存放在连续内存空间上的相同类型数据的集合。
特点
数组下标都是从0开始的。数组内存空间的地址是连续的
2、数组的元素是不能删的只能覆盖。
704. 二分查找
1、题目链接. - 力扣LeetCode
2、文章讲解代码随想录
3、视频讲解手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode704. 二分查找_哔哩哔哩_bilibili
4、题目
给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。
示例 1:
输入: nums [-1,0,3,5,9,12], target 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums [-1,0,3,5,9,12], target 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示
你可以假设 nums 中的所有元素是不重复的。n 将在 [1, 10000]之间。nums 的每个元素都将在 [-9999, 9999]之间。
5、前提条件数组为有序数组数组中无重复元素
5、难点对区间的定义没有想清楚区间的定义就是不变量
6、遵循点保证循环不变量原则要不左闭右闭要不左闭右开
左闭右闭写法
时间复杂度O(log n)空间复杂度O(1)
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;}
}
左闭右开写法
时间复杂度O(log n)空间复杂度O(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;}
}
27. 移除元素
1、题目链接. - 力扣LeetCode
2、文章讲解代码随想录
3、视频讲解数组中移除元素并不容易 | LeetCode27. 移除元素_哔哩哔哩_bilibili
4、题目
给你一个数组 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。
你不需要考虑数组中超出新长度后面的元素。
4、前提条件不要使用额外的数组空间你必须仅使用 O(1) 额外空间并原地修改输入数组元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
5、注意点数组的元素在内存地址中是连续的不能单独删除数组中的某个元素只能覆盖。 暴力解法
时间复杂度O(n^2)空间复杂度O(1)
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];}// 4.将数组长度减一i--;// 5.将返回数组长度减一size--;}}// 6.返回数组的长度return size;}
}
双指针解法
1、 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
2、定义快慢指针
快指针寻找新数组的元素 新数组就是不含有目标元素的数组慢指针指向更新 新数组下标的位置
时间复杂度O(n)空间复杂度O(1)
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;}
}
