Java二分查找算法与数组处理的应用实例

目录
  • 1.特殊数组的特征值
    • 题目描述
    • 思路详解
    • 代码与结果
  • 2.在D天内送达包裹的能力
    • 题目描述
    • 思路详解
    • 代码与结果
  • 3.咒语和药水的成功对数
    • 题目描述
    • 思路详解
    • 代码与结果
  • 总结

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;
    }
}

总结

今天主要集中在二分查找的应用,希望小伙伴通过今天的习题可以体验到二分查找的好处,可以更加熟练的应用哦!!!!

到此这篇关于Java二分查找算法与数组处理的应用实例的文章就介绍到这了,更多相关Java二分查找与数组内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java中数组容器(ArrayList)设的计与实现

    目录 ArrayList为我们提供了哪些功能 设计原理分析 代码实现 完整代码 本篇文章主要跟大家介绍我们最常使用的一种容器ArrayList.Vector的原理,并且自己使用Java实现自己的数组容器MyArrayList,让自己写的容器能像ArrayList那样工作.在本篇文章当中首先介绍ArrayList的一些基本功能,然后去分析我们自己的容器MyArrayList应该如何进行设计,同时分析我们自己的具体实现方法,最后进行代码介绍!!! ArrayList为我们提供了哪些功能 我们来看一个

  • Java 二分查找的实现及图例解析

    二分查找又称折半查找,它是一种效率较高的查找方法. 折半查找的算法思想是将数列按有序化(递增或递减)排列,查找过程中采用跳跃式方式查找,即先以有序数列的中点位置为比较对象,如果要找的元素值小于该中点元素,则将待查序列缩小为左半部分,否则为右半部分.通过一次比较,将查找区间缩小一半. 折半查找是一种高效的查找方法.它可以明显减少比较次数,提高查找效率.但是,折半查找的先决条件是查找表中的数据元素必须有序. 折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除

  • Java 二分查找算法的实现

    二分查找又称折半查找,它是一种效率较高的查找方法. 折半查找的算法思想是将数列按有序化(递增或递减)排列,查找过程中采用跳跃式方式查找,即先以有序数列的中点位置为比较对象,如果要找的元素值小 于该中点元素,则将待查序列缩小为左半部分,否则为右半部分.通过一次比较,将查找区间缩小一半. 折半查找是一种高效的查找方法.它可以明显减少比较次数,提高查找效率.但是,折半查找的先决条件是查找表中的数据元素必须有序. 折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删

  • 两种java实现二分查找的方式

    目录 1.二分查找算法思想 2.二分查找图示说明 3.二分查找优缺点 3.java代码实现 3.1 使用递归实现 3.1 不使用递归实现(while循环) 3.3 测试 4.时间复杂度 5.空间复杂度 起初在数据结构中学习递归时实现二分查找,实际上不用递归也可以实现,毕竟递归是需要开辟额外的空间的来辅助查询.本文就介绍两种方法 1.二分查找算法思想 有序的序列,每次都是以序列的中间位置的数来与待查找的关键字进行比较,每次缩小一半的查找范围,直到匹配成功. 一个情景:将表中间位置记录的关键字与查找

  • Java实现二分查找树及其相关操作

    二分查找树(Binary Search Tree)的基本操作有搜索.求最大值.求最小值.求前驱.求后继.插入及删除. 对二分查找树的进行基本操作所花费的时间与树的高度成比例.例如有n个节点的完全二叉树,对它进行的基本操作的时间复杂度为O(logn).然而,如果树是一个有n个节点的线性的链,则在这种情况下的时间复杂度为O(n). 1.什么是二分查找树 二分查找树是一种有组织的二叉树.我们可以通过链接节点表示这样一棵树.每个节点包含键(key),数据(data),左子节点(left),右子节点(ri

  • Java实例讲解多态数组的使用

    目录 多态概述 1.向上转型 2.向下转型 多态数组 Arrtest.java Person.java Student.java Teacher.java 多态数组+向下转型 instanceof关键字 Arrtest.java Person.java Student.java Teacher.java 多态概述 多态概念:所谓多态就是指程序中定义的引用变量所指向的具体类型和通过该引用变量发出的方法调用在编程时并不确定,而是在程序运行期间才确定,即一个引用变量到底会指向哪个类的实例对象,该引用变

  • Java数组与字符串深入探索使用方法

    目录 一.数组 1.数组的定义和内存分配 2.数组的初始化 3.数组的引用 4.二维数组 5.几点说明 二.字符串(String) 1.字符串的定义方法 2.字符串操作 lenth()方法 charAt() 方法 contains() 方法 replace() 方法 split() 方法 一.数组 数组是相同类型的数据按顺序组成的一种复合数据类型.通过数组名加数组下标,来使用数组中的数据. 数组对于每一门编程语言来说都是重要的数据结构之一,当然不同语言对数组的实现及处理也不尽相同. Java 语

  • Java数组与二维数组及替换空格实战真题讲解

    目录 数组中重复的数字 题目描述 思路详解 代码与结果 二维数组中的查找 题目描述 思路详解 代码与结果 替换空格 题目描述 思路详解 代码与结果 数组中重复的数字 题目描述 思路详解 本题的思路比较简单,首先将这个数组排序,遍历数组,找到当前的和前一个相同的直接输出就好了.没找到输出-1. 注意:这个方法要注意循环的时候下标要从1开始哦,不然会报数组下标异常滴. 代码与结果 import java.util.*; public class Solution { /** * 代码中的类名.方法名

  • Java二分查找算法与数组处理的应用实例

    目录 1.特殊数组的特征值 题目描述 思路详解 代码与结果 2.在D天内送达包裹的能力 题目描述 思路详解 代码与结果 3.咒语和药水的成功对数 题目描述 思路详解 代码与结果 总结 1.特殊数组的特征值 题目描述 思路详解 看到本题,首先思考需要排序,然后查找,这里为了效率采用二分查找. 假设定义x=(left+riht)/ 2,每次查找到nums中第一个大于等于X的元素下标,判断大于等于X的个数与X的关系,进行分情况修改左右边界. 代码与结果 class Solution { public

  • Java二分查找算法实现代码实例

    这篇文章主要介绍了Java二分查找算法实现代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 二分查找: 两种方式: 非递归方式和递归方式 主要思路: 对于已排序的数组(先假定是从小到大排序), 先定义两个"指针", 一个"指向"首元素low, 一个"指向"末尾元素high. 然后, 开始折半比较, 即让要查找的数与数组中间的元素(索引为 low+high/2)比较. 若要查找的数比中间数小

  • JavaScript使用二分查找算法在数组中查找数据的方法

    本文实例讲述了JavaScript使用二分查找算法在数组中查找数据的方法.分享给大家供大家参考.具体分析如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表.首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一

  • Java实现二分查找算法实例分析

    本文实例讲述了Java实现二分查找算法.分享给大家供大家参考.具体如下: 1. 前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序 2. 原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后:将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回.然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分.可能描述得不是很清楚,若是不理解可以去网上找.从描述上就可以看出这个算法适合

  • Java实现查找算法的示例代码(二分查找、插值查找、斐波那契查找)

    目录 1.查找概述 2.顺序查找 3.二分查找 3.1 二分查找概述 3.2 二分查找实现 4.插值查找 4.1 插值查找概述 4.2 插值查找实现 5.斐波那契查找 5.1 斐波那契查找概述 5.2 斐波那契查找实现 5.3 总结 1.查找概述 查找表: 所有需要被查的数据所在的集合,我们给它一个统称叫查找表.查找表(Search Table)是由同一类型的数据元素(或记录)构成的集合. 查找(Searching): 根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录).

  • 使用PHP实现二分查找算法代码分享

    第一种方法: [二分查找要求]:1.必须采用顺序存储结构 2.必须按关键字大小有序排列. [优缺点]折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表. [算法思想]首先,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表. 复制代码 代码如下: <?

  • PHP二分查找算法示例【递归与非递归方法】

    本文实例讲述了PHP二分查找算法.分享给大家供大家参考,具体如下: binarySearch 二分查找采用的方法比较容易理解,以数组为例: ① 先取数组中间的值floor((low+top)/2), ② 然后通过与所需查找的数字进行比较,若比中间值大,则将首值替换为中间位置下一个位置,继续第一步的操作:若比中间值小,则将尾值替换为中间位置上一个位置,继续第一步操作 ③ 重复第二步操作直至找出目标数字 比如从1,3,9,23,54 中查找数字23, 首位置为0, 尾位置为4,中间位置就为2 值为9

  • 二分查找算法在C/C++程序中的应用示例

    二分查找算法的思想很简单,<编程珠玑>中的描述: 在一个包含t的数组内,二分查找通过对范围的跟综来解决问题.开始时,范围就是整个数组.通过将范围中间的元素与t比较并丢弃一半范围,范围就被缩小.这个过程一直持续,直到在t被发现,或者那个能够包含t的范围已成为空.         Donald Knuth在他的<Sorting and Searching>一书中指出,尽管第一个二分查找算法早在1946年就被发表,但第一个没有bug的二分查找算法却是在12年后才被发表出来.其中常见的一个

随机推荐