LeetCode 剑指Offer53.在排序数组中查找数字
2021/6/17 19:02:49
本文主要是介绍LeetCode 剑指Offer53.在排序数组中查找数字,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
统计一个数字在排序数组中出现的次数。
思路
遍历,计数
代码
class Solution { public int search(int[] nums, int target) { int count = 0; for(int i = 0 ; i < nums.length ; i++){ if(nums[i] == target) count ++; } return count ; } }
优化
忽略了重要信息:排序过的数组
题解
二分搜索
class Solution { public int search(int[] nums, int target) { // 搜索右边界 right int i = 0, j = nums.length - 1; while(i <= j) { int m = (i + j) / 2; if(nums[m] <= target) i = m + 1; else j = m - 1; } int right = i; // 若数组中无 target ,则提前返回 if(j >= 0 && nums[j] != target) return 0; // 搜索左边界 right i = 0; j = nums.length - 1; while(i <= j) { int m = (i + j) / 2; if(nums[m] < target) i = m + 1; else j = m - 1; } int left = j; return right - left - 1; } } 作者:jyd
反思总结
1 思想类似于二分查找,区别还是有的。
2 寻找左边界,只要nums[mid]还大于等于target,j就继续往左逼近。
3 寻找有边界 , 只要nums[mid] 还小于等于target ,i 继续向右毕竟。
这篇关于LeetCode 剑指Offer53.在排序数组中查找数字的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-20whatsapp webhook 回调的签名验证偶尔会失败是什么原因-icode9专业技术文章分享
- 2024-09-19Excel数据导出课程:初学者必备教程
- 2024-09-19Excel数据导入课程:新手入门指南
- 2024-09-19RBAC的权限管理入门教程
- 2024-09-19如何使用Svg Sprite Icon制作图标
- 2024-09-19uniapp 如何实现点赞后全局更新数据-icode9专业技术文章分享
- 2024-09-19云函数怎么运行wx-server-sdk-icode9专业技术文章分享
- 2024-09-19"dependencies": { "wx-server-sdk": "latest" },是什么意思-icode9专业技术文章分享
- 2024-09-16优化批处理流程:自定义BatchProcessorUtils的设计与应用
- 2024-09-15laravel collect游标批量插入的方法示例-icode9专业技术文章分享