摘要:算法训练营核心考点数组相关,特性观察,时间复杂度把握核心考点数组理解,二分查找,临界条件核心考点数组操作,排序思想的扩展使用核心考点数组相关,特性观察,时间复杂度把握注意查找的过程本质是排除的过程。
注意:
1.查找的过程本质是排除的过程。
2.一次排除一行或一列。
3.从左上角或者右下角开始,可以一次排除一行或者一列
int i = 0;int j = array[0].size()-1;while( i < array.size() && j >= 0){ if(target < array[i][j]){ //array[i][j]一定是当前行最大的,当前列最小的 //target < array[i][j] 排除当前列 j--; } else if(target > array[i][j]){ //target > array[i][j] 排除当前行 i++; } else{ //找到 return true; } } return false; }};
这道题第一种方法就是遍历一遍找最小的数,这里我们把代码附上就不详细讲了。
class Solution {public: int minNumberInRotateArray(vector<int> rotateArray) { if (rotateArray.empty()) { return 0; } int i = 0; int lit = rotateArray[0]; for (i = 0; i < rotateArray.size(); i++) { if (rotateArray[i] < lit) { lit = rotateArray[i]; } } return lit; }};
第二种方法:采用二分查找的方式,进行定位。
定义首尾下标,因为是非递减数组旋转,所以旋转最后可以看做成两部分,前半部分整体非递减,后半部分整体非递减,前半部分整体大于后半部分。
所以,我们假设如下定义,left指向最左侧,right指向最右侧,mid为二分之后的中间位置,逐步缩减范围,/当left和right相邻时,right指向的位置,就是最小元素的位置。
class Solution {public: int minNumberInRotateArray(vector<int> rotateArray) { int left = 0; int right = rotateArray.size() - 1; int mid = (left + right) >> 1; while (rotateArray[left] >= rotateArray[right]) { if (right - left == 1) { mid = right; break; } mid = left + ((right - left) >> 1); if (rotateArray[mid] == rotateArray[left] && rotateArray[left] == rotateArray[right]) { int result = rotateArray[left]; for (int i = left + 1; i < right; i++) { if (result>rotateArray[i]){ result = rotateArray[i]; } } return result; } if (rotateArray[left] <= rotateArray[mid]) { left = mid; } else { right = mid; } } return rotateArray[mid]; }};
我们先求出来奇数,然后将这个奇数保存起来,将该奇数之前的内容(偶数序列),整体后移一个位置将奇数保存在它将来改在的位置,因为我们是从左往右放的,没有跨越奇数,所以一定是相对位置不变的。
int i = 0; int k = 0; for (i = 0; i < array.size() - 1; i++) { if (array[i] & i == 1) { int tmp = array[i]; int j = i; while (j>0) { array[j] = array[j - 1]; j--; } array[k++] = tmp; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/119132.html
摘要:导入库导入数据集这一步的目的是将自变量和因变量拆成一个矩阵和一个向量。 数据预处理是机器学习中最基础也最麻烦的一部分内容在我们把精力扑倒各种算法的推导之前,最应该做的就是把数据预处理先搞定在之后的每个算法实现和案例练手过程中,这一步都必不可少同学们也不要嫌麻烦,动起手来吧基础比较好的同学也可以温故知新,再练习一下哈 闲言少叙,下面我们六步完成数据预处理其实我感觉这里少了一步:观察数据...
摘要:更新今天又发现了一种简单的方法可以直接对年月日时分秒进行操作,假如今天那么所得昨天为昨天的时间前天的时间其中,函数为扩展函数。 1、时间格式化 1 //昨天的时间 2 var day1 = new Date(); 3 day1.setTime(day1.getTime()-24*60*60*1000); 4 var s1 = day1.getFullYear()+- + (da...
摘要:更新今天又发现了一种简单的方法可以直接对年月日时分秒进行操作,假如今天那么所得昨天为昨天的时间前天的时间其中,函数为扩展函数。 1、时间格式化 1 //昨天的时间 2 var day1 = new Date(); 3 day1.setTime(day1.getTime()-24*60*60*1000); 4 var s1 = day1.getFullYear()+- + (da...
摘要:更新今天又发现了一种简单的方法可以直接对年月日时分秒进行操作,假如今天那么所得昨天为昨天的时间前天的时间其中,函数为扩展函数。 1、时间格式化 1 //昨天的时间 2 var day1 = new Date(); 3 day1.setTime(day1.getTime()-24*60*60*1000); 4 var s1 = day1.getFullYear()+- + (da...
摘要:但是在这个过程中,遇到了一个请求无法获取到的问题。解决办法安装包再次打印三接下来几天需要完成的工作大概看一下的并各写一篇博客登录和注册应该使用有关的知识了解一下并写一篇博客。 vue nuxt koa2 mongodb 写博客(Day1) 一.利用nuxt初始化项目 初始化项目有两种方法: 1.vue init nuxt-community/koa-template 此种方法...
阅读 2144·2021-11-22 09:34
阅读 2285·2021-11-19 09:40
阅读 1003·2021-10-20 13:48
阅读 1834·2021-09-30 09:47
阅读 2903·2021-09-28 09:36
阅读 1337·2021-09-07 09:59
阅读 1266·2021-09-04 16:45
阅读 2125·2019-08-30 15:56