【LEETCODE】32、LeetCode的第35题，查找插入的位置
2024-08-31 03:55:16
凉凉，看来想做好一个题还不容易啊。。。
有点难受。。。
1.看看题目吧
Given a sorted array and a target value, return the index if the target is found. If not,
return the index where it would be if it were inserted in order. You may assume no duplicates in the array.
给定一个有序数组，依旧是二分查找，不同之处是如果没有找到指定数字，需要返回这个数字应该插入的位置。
本来想想着不就二分查找嘛，分分钟搞定。。。结果悲剧了，小瞧了这题了，活活被气死
2.上代码
废话不多说了，可恶上代码吧
先来看看悲剧版本1：
class Solution {
public int searchInsert(int[] nums, int target) {
//这个题类似之前去小米面试的题，用二分查找
int start = 0, end = nums.length - 1;
int result = -1;
while(start < end) {
//注意判断当找到的位置值比target大，那么说明数据在左边，如果比target小，那么数据在右边
int mid = (start +end)/2;
if(nums[mid] == target) {
result = mid;
break;
} else if(nums[mid] < target) {
start = mid;
} else {
end = mid;
}
}
//最后如果start == end
if(start == end) {
if(start == 0) {
result = 0;
} else if(nums[start] > target) {
//如果这个时候比targe大，那么就是前一位
result = start - 1;
} else {
result = start + 1;
}
}
return result;
}
}
简简单单，3分钟写完。。。然后分分钟悲剧。。。
兄弟们，这个玩意是个死循环。。。。
比如：最后start = 0, end = 1; 那么结果就是mid =0,start=0,end=1,MMP停不下来啊
问题在于，我们如果除数为0的话，那么start = mid，然后我们
nums[mid] < target的时候，start=mid 其实就是没变，还是等于start，永远不会达到条件start>=end的情况 悲剧版本2：
class Solution {
public int searchInsert(int[] nums, int target) {
//这个题类似之前去小米面试的题，用二分查找
int start = 0, end = nums.length - 1;
int result = -1;
while(start < end) {
//注意判断当找到的位置值比target大，那么说明数据在左边，如果比target小，那么数据在右边
int mid = (start + end) / 2;
if(nums[mid] == target) {
result = mid;
break;
} else if(nums[mid] < target) {
start = mid + 1;
} else {
end = mid;
}
}
//最后如果start == end
if(start == end) {
if(start == 0) {
result = 0;
} else if(nums[start] > target) {
//如果当前位置比这个值大，那么说明当前的值是用来取代这个位置的
result = start;
} else {
//如果比这个值小，那么就应该往后移一位
result = start + 1;
}
}
return result;
}
}
哎，一把辛酸泪，试试nums=[1],val=2吧，你会发现，循环根本没进去，然后start永远==0，那么结果就是0，MMP
行吧，行吧，我把start==0的判断去掉还不行么
悲剧版本3：
class Solution {
public int searchInsert(int[] nums, int target) {
//这个题类似之前去小米面试的题，用二分查找
int start = 0, end = nums.length - 1;
int result = -1;
while(start < end) {
//注意判断当找到的位置值比target大，那么说明数据在左边，如果比target小，那么数据在右边
int mid = (start + end) / 2;
if(nums[mid] == target) {
result = mid;
break;
} else if(nums[mid] < target) {
start = mid + 1;
} else {
end = mid;
}
}
//最后如果start == end
if(start == end) {
if(nums[start] > target) {
//如果当前位置比这个值大，那么说明当前的值是用来取代这个位置的
result = start;
} else {
//如果比这个值小，那么就应该往后移一位
result = start + 1;
}
}
return result;
}
}
哎呀，能不能一次到位啊，气死啦。。。。
不说了nums={1},val = 1....
好绝望啊，这个时候这个代码会返回1，为啥，我开始以为while找到了，但是没有返回，然后进入了下面的if判断
我改。。。
悲剧版本4：
class Solution {
public int searchInsert(int[] nums, int target) {
//这个题类似之前去小米面试的题，用二分查找
int start = 0, end = nums.length - 1;
int result = -1;
while(start < end) {
//注意判断当找到的位置值比target大，那么说明数据在左边，如果比target小，那么数据在右边
int mid = (start + end) / 2;
if(nums[mid] == target) {
return mid;
} else if(nums[mid] < target) {
start = mid + 1;
} else {
end = mid;
}
}
//最后如果start == end
if(start == end) {
if(nums[start] > target) {
//如果当前位置比这个值大，那么说明当前的值是用来取代这个位置的
result = start;
} else {
//如果比这个值小，那么就应该往后移一位
result = start + 1;
}
}
return result;
}
}
他娘的，其实它while根本就没进去。。。。
绝望*n
哎，其实这里是漏掉了考虑没有进循环，然后start的位置正好就是找到了的位置。。。
改呗。。。
class Solution {
public int searchInsert(int[] nums, int target) {
//这个题类似之前去小米面试的题，用二分查找
int start = 0, end = nums.length - 1;
int result = -1;
while(start < end) {
//注意判断当找到的位置值比target大，那么说明数据在左边，如果比target小，那么数据在右边
int mid = (start + end) / 2;
if(nums[mid] == target) {
return mid;
} else if(nums[mid] < target) {
start = mid + 1;
} else {
end = mid;
}
}
//最后如果start == end
if(start == end) {
if(nums[start] >= target) {
//如果当前位置比这个值大或相等，那么正好是这个位置，那么说明当前的值是用来取代这个位置的
result = start;
} else {
//如果比这个值小，那么就应该往后移一位
result = start + 1;
}
}
return result;
}
}
终于过关了。。。不容易啊
不过这里还可以优化一下运算，那就是用位运算取代/运算
class Solution {
public int searchInsert(int[] nums, int target) {
//这个题类似之前去小米面试的题，用二分查找
int start = 0, end = nums.length - 1;
int result = -1;
while(start < end) {
//注意判断当找到的位置值比target大，那么说明数据在左边，如果比target小，那么数据在右边
int mid = start + ((end - start) >>> 1);
if(nums[mid] == target) {
return mid;
} else if(nums[mid] < target) {
start = mid + 1;
} else {
end = mid;
}
}
//最后如果start == end
if(start == end) {
if(nums[start] >= target) {
//如果当前位置比这个值大或相等，那么正好是这个位置，那么说明当前的值是用来取代这个位置的
result = start;
} else {
//如果比这个值小，那么就应该往后移一位
result = start + 1;
}
}
return result;
}
}
到这里就差不多了！！
最新文章
- 命名不规范引发的DropDownListFor无法选中
- Zabbix3.0 自动微信报障
- 找规律/数位DP HDOJ 4722 Good Numbers
- HighCharts入门
- CURL学习和应用
- REG_SZ和REG_EXPAND_SZ的区别
- 跨应用Session共享
- js处理日期的一些整理(js获取给定日期前一天的日期)
- 几款jQuery右键菜单插件
- DataGridView绘制序号
- Oracle 新增表空间文件
- SqlServer之触发器
- IOS UI 第八篇：基本UI
- vue视频学习笔记07
- 使用NPOI导出导入导出Excel
- 201771010126 王燕《面向对象程序设计（Java）》第十七周学习总结
- c++ map 注意事项
- Subplot 多合一显示
- Nginx 慢启动与拥塞窗口
- 黑色背景下 vs把{}括号变黑问题