剑指 Offer 53 - I. 在排序数组中查找数字 I + 二分法
2024-09-01 16:27:31
剑指 Offer 53 - I. 在排序数组中查找数字 I
Offer_53_1
题目描述
方法一：使用HashMap
package com.walegarrett.offer;
/**
* @Author WaleGarrett
* @Date 2021/2/9 20:10
*/
import java.util.HashMap;
import java.util.Map;
/**
* 题目描述：统计一个数字在排序数组中出现的次数。
*/
/**
* 方法一：使用HashMap存储数字出现的次数
*/
public class Offer_53 {
public int search(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<>();
for(int num : nums){
int val = map.getOrDefault(num, 0);
val++;
map.put(num, val);
}
return map.getOrDefault(target, 0);
}
}
方法二：二分法分别找上下边界
/**
* 方法二：使用二分法
*/
class Offer_53_2 {
public int search(int[] nums, int target) {
int len = nums.length;
int i=0, j = len-1;
while(i<=j){
int mid = (i+j)>>1;
if(nums[mid] <= target){
i= mid+1;
}else j= mid-1;
}
int right = i;
i=0; j = len-1;
while(i<=j){
int mid = (i+j)>>1;
if(nums[mid] < target){
i= mid+1;
}else j= mid-1;
}
int left = j;
return right-left-1;
}
}
复杂度分析
- 时间复杂度 O(log N) ： 二分法为对数级别复杂度。
- 空间复杂度 O(1) ： 几个变量使用常数大小的额外空间。
最新文章
- C# XML转JSON，不引用第三方JSON.NET类库
- JDBC API Description
- HttpClient
- 自制工具：迅速打开一个Node 环境的Playground
- 小白学数据分析----->付费用户生命周期研究
- Jfinal极速开发微信系列教程（一）--------------Jfinal_weixin demo的使用分析
- Server.MapPath() 解析
- JQ 复制节点
- 移动M站建设
- ubuntu 编译android源码
- Android 反射-换一种方式编程
- Java工程师：四个月小白变大咖，你能做到吗？
- ELK日志分析方案
- sql将服务器名称换成本地IP
- Redis更新的正确方法
- pandas 数据结构基础与转换
- c#中(&&,||)与(&,|)的区别和应用
- php git pull
- sql批量修改wordpress网站的文章发布状态
- PageUtil 分页