Java二分查找算法与数组处理的应用实例
作者:风铃听雨~ 发布时间:2022-07-11 01:26:57
标签:Java,二分查找,数组
1.特殊数组的特征值
题目描述
思路详解
看到本题,首先思考需要排序,然后查找,这里为了效率采用二分查找。
假设定义x=(left+riht)/ 2,每次查找到nums中第一个大于等于X的元素下标,判断大于等于X的个数与X的关系,进行分情况修改左右边界。
代码与结果
class Solution {
public int specialArray(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
int left = 0, right = n;
while (left <= right) {
int x = (left + right) >> 1;
int idx = binarySearch(nums, x); // nums中第一个大于等于x的元素位置
if (x == n - idx) {
return x;
} else if (x < n - idx) { // 大于等于x的元素太多了,所以下一轮搜索要增大x的取值范围
left = x + 1;
} else { // 反之,减少x的取值范围
right = x - 1;
}
}
return -1;
}
private static int binarySearch(int[] nums, int x) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) >> 1;
int val = nums[mid];
if (val >= x) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
}
2.在D天内送达包裹的能力
题目描述
思路详解
假设当船的运载能力为 x 时,我们可以在days 天内运送完所有包裹,那么只要运载能力大于 x,我们同样可以在 days 天内运送完所有包裹:我们只需要使用运载能力为 x时的运送方法即可。
由于必须按照数组weights 中包裹的顺序进行运送,因此我们从数组 weights 的首元素开始遍历,将连续的包裹都安排在同一天进行运送。当这批包裹的重量大于运载能力 x 时,我们就需要将最后一个包裹拿出来,安排在新的一天,并继续往下遍历。当我们遍历完整个数组后,就得到了最少需要运送的天数。
代码与结果
class Solution {
public int shipWithinDays(int[] weights, int days) {
// 确定二分查找左右边界
int left = Arrays.stream(weights).max().getAsInt(), right = Arrays.stream(weights).sum();
while (left < right) {
int mid = (left + right) / 2;
// need 为需要运送的天数
// cur 为当前这一天已经运送的包裹重量之和
int need = 1, cur = 0;
for (int weight : weights) {
if (cur + weight > mid) {
++need;
cur = 0;
}
cur += weight;
}
if (need <= days) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
3.咒语和药水的成功对数
题目描述
思路详解
本题采用二分查找的方法进行解题。
首先我们对药水的数组进行排序,其次我们遍历咒术数组,利用二分查找的思想在药水数组中查找,与成功值最接近的数值,存入到答案数组中。
有个小细节,判断时候1l * power * potions[mid] < success 这样做是为了把数字转化为long型,避免错误哦。
代码与结果
class Solution {
public int[] successfulPairs(int[] spells, int[] potions, long success) {
int[] ans = new int[spells.length];
Arrays.sort(potions);
for (int i = 0; i < spells.length; i++) {
int power = spells[i];
int left = 0;
int right = potions.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (1l * power * potions[mid] < success) {
left = mid + 1;
} else {
right = mid - 1;
}
}
ans[i] = potions.length - left;
}
return ans;
}
}
来源:https://blog.csdn.net/muzi_longren/article/details/125735530
0
投稿
猜你喜欢
- 0、前言本文主要对几种常见Java序列化方式进行实现。包括Java原生以流的方法进行的序列化、Json序列化、FastJson序列化、Pro
- 下截JNative组件jnative.sourceforge.net/ 到这里下载JNative开源项目,我下载的是1.3.2解压JNati
- 前言 短时间提升自己最快的手段就是背面试题,最近总结了Java常用的面试题,分享给大家,希望大家都能圆梦大厂,加油,我命由我不由天
- 本文实例为大家分享了java实现2048小游戏的具体代码,供大家参考,具体内容如下效果图:游戏介绍:1.2048是一款益智类小游戏,刚开始随
- 一、注解是什么Java 注解用于为 Java 代码提供元数据,看完这句话也许你还是一脸懵逼,用人话说就是注解不直接影响你的代码执行,仅提供信
- 问题在使用 Abp 框架的后台作业时,当后台作业抛出异常,会导致整个程序崩溃。在 Abp 框架的底层执行后台作业的时候,有 try/catc
- 使用foreach循环的坑我们首先看一段MyBatis中使用foreach循环的sql:SELECT * FROM table where
- 前言在日常开发中,除了修改请求参数、设置响应header,响应body外,还有一种需求就是url重新,或者是修改url,这里简述一下怎么在z
- 一:什么是classpath?classpath指的就是 *.java文件,资源文件等编译后存放的位置,对于maven项目就是指 targe
- 引言java中的Math.random()是一个在[0,1)范围等概率返回double数值类型的算法,基于此函数,我们来延申一些随机概率算法
- 前言Future的问题写多线程程序的时候,可以使用Future从一个异步线程中拿到结果,但是如果使用过程中会发现一些问题:如果想要对Futu
- 比如在类上使用该注解 @Alias("dDebtEntity")则在mapper.xml文件中resultType=&q
- 程序员日常工作中,发送http请求特别常见。本文以Java为例,总结发送http请求的多种方式。1. HttpURLConnection使用
- java修改JFrame默认字体修改默认字体的方法很简单。首先我们随便写一个按钮出来:import javax.swing.*; publi
- 一. 安装依赖包yum install -y wgetyum install -y gcc-c++yum install -y zlib-d
- 前言最近在刷java面试题偶然看到这类问题(try/finally中含有return时的执行顺序),觉得挺有意思于是小小的研究了一下,希望经
- 最近在做项目的过程中 需要用JWT做登录和鉴权 查了很多资料 都不甚详细有的是需要在application.yml里进行jwt的配置 但我在
- 条件:1、android:ellipsize=”marquee”2、TextView必须单行显示,即内容必须超出TextView
- 在Java中创建一个线程有两种方法:继承Thread类和实现Runnable接口。下面通过两个例子来分析两者的区别:1)继承Thread类p
- 本文实例为大家分享了java中文传值乱码问题,以及解决方法,供大家参考,具体内容如下一般编码格式设置:1.可以经过两次编码处理,即设置字符集