网站设计欣赏中国,杭州市江干建设局网站,营销技巧有哪些方面,网上挣钱正规渠道文章目录题目思路如何建立左右区间#xff1f;如何查找最高点#xff1f;那我们怎么判断 num 到底处于什么样的位置呢#xff1f;如何确定插入位置#xff1f;插入元素代码题目
给一个只循环递增一次的数组 res#xff0c;res 满足首元素大于等于尾元素#xff0c;形如如何查找最高点那我们怎么判断 num 到底处于什么样的位置呢如何确定插入位置插入元素代码题目
给一个只循环递增一次的数组 resres 满足首元素大于等于尾元素形如 456724 再给出一个整型数字 num将其插入到数组中应在的位置。
示例
输入 res 456724 num 3 输出 4567234 思路
用二分查找确定应该插入的位置难点在于左右区间的建立。
如何建立左右区间
首先明确两点对于整个数组而言
首元素一定 大于等于 尾元素以数组的最大值为界限最大值左边的元素一定 大于等于 右边的元素
用图像表示数组是这样的黑色表下标紫色表值
我们可以看到要插入的元素无非在最高点的左边或右边自下文始最高点用high替代首元素位置用begin表示尾元素位置用last表示
当 num 处于最高点左边时二分查找的范围应该是 [begin, high]当 num 处于最高点右边时二分查找的范围应该是 [high1last]
也就是说划定二分查找范围左右区间的建立的重中之重在于最高点的确定。
如何查找最高点
个人想到两种方法
遍历查找时间复杂度O(n)
算法思想没有什么多说的中规中矩的遍历。
int high 0;
for (int i 1; i res.size(); i) {if (res[high] res[i]) {break;}high i;
}二分查找时间复杂度O(log2n)
算法思想是:
先以数组首元素、尾元素作为二分查找的左右边界中间元素暂定为high以 左边界小于右边界 作为while的循环条件首先判断此时的high是否大于首元素大于首元素证明此时的high处于 真正最高点的左边 或 就是真正最高点此时需要判定high1中元素和high中元素之间的关系 如果high1中元素大于high中元素表明 真正最高点应该在high的左边因此更新左边界—— left high 1如果high1中元素小于high中元素表明 high即为真正最高点 因此break出while循环即可 小于首元素证明此时的high处于 真正最高点的右边 此时需要判定high和high-1所指元素之间的关系 如果 res[high - 1] res[high] 如举例中high6时43表明最高点仍在 high-1的左边也就是high-1也处于真正最高点的右边因此要更新右边界—— right high - 2如果 res[high - 1] res[high] 此时表明high-1即为最高点因此将high–并break出while循环即可 每次循环更新完左右边界之后需要更新high值—— high left (right - left) / 2;跳出while循环得到的high即为最高点的位置
int size res.size() - 1;
int left 0;
int right size;
int high left (right - left) / 2;
int flag res[0];
while (left right) {if (res[high] flag) {if (res[high 1] res[high]) {left high 1;}else {break;}}else {if (res[high - 1] res[high]) {right high - 2;}else {high--;break;}}high left (right - left) / 2;
}那我们怎么判断 num 到底处于什么样的位置呢
这时应该结合之前我们说到的一句话
首元素一定 大于等于 尾元素
那我们做个归纳如果
num res[0] num 处于 high 左边res[end] num res[0] num 处于 high 右边插入到尾元素的位置res[end] num res[0] 不可能出现这种情况因为这种情况下num没有位置可以插入。res[end] num res[0] num 处于 high 左边插入到首元素的位置res[end] num num 处于 high 右边
第二点和第四点是什么意思呢
关于第二点我们举这样一个例子
输入 res 56724 num 5 输出 res 567245 关于第四点我们举这样一个例子
输入 res 67245 num 5 输出 res 567245 因此根据上面的归纳我们可以得到代码
注意因为第三种情况不可能出现因此我们在描述第2、4种情况时可以省略大小比较因为当2、4种描述的等于关系成立时大小关系必然成立。
if (res[size] num || num res[0]) { // num处于high右边left high 1;right size;
}
if(num res[0] || num res[size]) { // num处于high左边left 0;right high;
} 如何确定插入位置
建立好左右边界后就可以根据二分查找来确定插入位置了。
当左边界小于右边界时执行二分查找。中间点mid对应的元素小于 num 时左边界更改为 mid1 。mid 对应的元素大于 num 时右边界更改为 mid-1 。
int mid left (right - left) / 2;
while (left right)
{if (res[mid] num) {left mid 1; }else {right mid - 1;}mid left (right - left) / 2;
} 插入元素
最终使用insert函数进行插入
res.insert(res.begin() mid, num);insert会将给定值插入到给定位置之前。 代码
class Solution {
public:vectorint fun(vectorint res, int num) {int size res.size() - 1;int left 0;int right size;/*int high 0;for (int i 1; i res.size(); i) {if (res[high] res[i]) {break;}high i;}*/// 与上面注释部分一样都是查最高点int high left (right - left) / 2;int flag res[0];while (left right) {if (res[high] flag) {if (res[high 1] res[high]) {left high 1;}else {break;}}else {if (res[high - 1] res[high]) {right high - 2;}else {high--;break;}}high left (right - left) / 2;}// 确定左右边界if (res[size] num || num res[0]) { // num处于high右边left high 1;right size;}if(num res[0] || num res[size]) { // num处于high左边left 0;right high;} // 确定插入位置int mid left (right - left) / 2;while (left right){if (res[mid] num) {left mid 1; }else {right mid - 1;}mid left (right - left) / 2;} res.insert(res.begin() mid, num);return res;}
};用例测试
int main() {Solution s;vectorint iv { 4,5,6,7,1,2,4 };int num 3;iv s.fun(iv, num);for (auto i iv.begin(); i ! iv.end(); i) {cout *i ;}cout endl;
}
