郑州网站建设 郑州网站制作,哪个网站找人做网页比较好,效果好企业营销型网站建设,昆明做网站优化数组理论基础
数组是存放在连续内存空间上的相同类型数据的集合#xff0c;可以方便的通过下标索引的方式获取到下标下对应的数据。 1.数组下标都是从0开始的。
2.数组内存空间的地址是连续的。
正是因为数组的在内存空间的地址是连续的#xff0c;所以我们在删除或者增添…数组理论基础
数组是存放在连续内存空间上的相同类型数据的集合可以方便的通过下标索引的方式获取到下标下对应的数据。 1.数组下标都是从0开始的。
2.数组内存空间的地址是连续的。
正是因为数组的在内存空间的地址是连续的所以我们在删除或者增添元素的时候就难免要移动其他元素的地址所以数组的元素是不能删的只能覆盖。 在C中二维数组在内存的空间地址是连续但在java中并不是连续的。
java中的数组排列方式如下所以Java的二维数组在内存中不是 3*4 的连续地址空间而是四条连续的地址空间组成 算法题
Leetcode 704.二分查找
题目链接:二分查找
大佬视频讲解手把手带你撕出正确的二分法 个人思路
题目要求是用二分法那具体步骤为找到数组中间的值将这个值循环与目标值对比1.若找到目标值放回下标2.没找到目标值的话则按照与目标值对比的大小重新选择范围再选择这个范围中的中间值继续对比但这其中比较难解决的是范围的确定。
解法
这道题目的前提是数组为有序数组同时题目还强调数组中无重复元素因此以后遇到此种类型都可以考虑使用二分法
二分法中对区间的定义很重要。区间的定义就是不变量。要在二分查找的过程中保持不变量就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作这就是循环不变量规则。 二分法第一种写法:左闭右闭
即[left, right]左闭右闭要注意以下两点
循环while中的判断条件 “(left right) ”要使用 因为left right是有意义的。目标值小于中间值右区间需要改变时right 要赋值为 mid - 1因为当前这个nums[middle]一定不是target。
class Solution {public int search(int[] nums, int target) {int left0;int rightnums.length-1;//定义target在左闭右闭的区间里[left, right]if(target nums[0]||targetnums[right-1]){//避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算return -1;}while(leftright){int midleft((right-left)1);//防止溢出; 是右移位运算符,相当于除以 2 并向下取整if(nums[mid]target){return mid;}else if(nums[mid]target){//target 在右区间即[mid 1, right]leftmid1;}else if(nums[mid]target){//target 在左区间即[left, mid- 1]rightmid-1;}}return -1;}
}
时间复杂度:O(log n)折半循环
空间复杂度:O(1);没有使用多余空间 二分法第二种写法:左闭右开
即[left, right)左闭右开要注意以下两点
循环while中的判断条件“(left right)”这里使用 ,因为left right在区间[left, right)是没有意义的目标值小于中间值右区间需要改变时 right 更新为 mid因为下一个查询区间不会去比较nums[middle]
class Solution {public int search(int[] nums, int target) {int left0;int rightnums.length;//定义target在左闭右开的区间里[left, right]if(target nums[0]||targetnums[right-1]){//避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算return -1;}while(leftright){int midleft((right-left)1);//防止溢出; 是右移位运算符,相当于除以 2 并向下取整if(nums[mid]target){return mid;}else if(nums[mid]target){//target 在右区间即[mid 1, right)leftmid1;}else if(nums[mid]target){//target 在左区间即[left, mid)rightmid;}}return -1;}
}
时间复杂度:O(log n)折半循环
空间复杂度:O(1);没有使用多余空间 Leetcode27.移除元素
题目链接:27.移除元素
大佬视频讲解数组中移除元素并不容易 个人思路
因为数组的元素在内存地址中是连续的不能单独删除数组中的某个元素只能覆盖所以若要暴力解决的话得两次循环一次循环找与目标值对应的二次循环将删除元素其后面的元素向前赋值
这种解法慢也可以换成双指针来解决指针分为快慢指针快指针找需要删除的元素慢指针找新数组的下标 解法
暴力解法
双重循环
class Solution {public int removeElement(int[] nums, int val) {int len nums.length;for (int i 0; i len; i) {if (nums[i] val) { // 发现需要移除的元素就将数组集体向前移动一位for (int j i 1; j len; j) {nums[j - 1] nums[j];}i--; // 因为下标i以后的数值都向前移动了一位所以i也向前移动一位len--; // 此时数组的大小-1}}return len;}
}
时间复杂度:O(n^2)两个for循环 n*n
空间复杂度:O(1);没有使用多余空间 快慢双指针
搞清楚双指针的定义非常关键快指针的作用是寻找新数组的元素 新数组就是不含有目标元素的数组慢指针的作用是指向更新 新数组下标的位置 class Solution {public int removeElement(int[] nums, int val) {int slow0;//慢指针for(int fast0;fastnums.length;fast){if(nums[fast]!val){//如果没有找到目标元素则一起向前遍历nums[slow]nums[fast];slow;}}return slow;}
}
时间复杂度:O( n)一个for循环
空间复杂度:O(1);没有使用多余空间 以上是个人的思考反思与总结若只想根据系列题刷参考卡哥的网址代码随想录算法官网
