亲宝软件园·资讯

展开

Java二分查找与数组

风铃听雨~ 人气:0

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

总结

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

加载全部内容

相关教程
猜你喜欢
用户评论