通知
此博客运行在jpress系统上,如果你喜欢此博客模板,请加QQ群:1061691290(whimurmur模板/jpress插件),免费下载使用

leetcode探索之二分查找学习 模板 III

866人浏览 / 0人评论 | 作者:whisper  | 分类: 设计模式与算法  | 标签: 设计模式与算法  /  leetcode  | 

作者:whisper

链接:http://proprogrammar.com:443/article/636

声明:请尊重原作者的劳动,如需转载请注明出处


    本章展示了模板 #3 的代码片段。它简要说明了何时使用该模板,并强调了这 3 个模板之间的关键语法差异。

    二分查找模板 III

    模板 #3:

int binarySearch(int[] nums, int target) {
    if (nums == null || nums.length == 0)
        return -1;

    int left = 0, right = nums.length - 1;
    while (left + 1 < right){
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid;
        } else {
            right = mid;
        }
    }

    // Post-processing:
    // End Condition: left + 1 == right
    if(nums[left] == target) return left;
    if(nums[right] == target) return right;
    return -1;
}

    模板 #3 是二分查找的另一种独特形式。 它用于搜索需要访问当前索引及其在数组中的直接左右邻居索引的元素或条件。

    关键属性

  • 实现二分查找的另一种方法。
  • 搜索条件需要访问元素的直接左右邻居。
  • 使用元素的邻居来确定它是向右还是向左。
  • 保证查找空间在每个步骤中至少有 3 个元素。
  • 需要进行后处理。 当剩下 2 个元素时,循环 / 递归结束。 需要评估其余元素是否符合条件。

    区分语法

  • 初始条件:left = 0, right = length-1
  • 终止:left + 1 == right
  • 向左查找:right = mid
  • 向右查找:left = mid

    算法-在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值,返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
class Solution {
    // 想法:先二分找到一个目标值,再以这个值为分界向两侧二分查找相同的目标值
    public int[] searchRange(int[] nums, int target) {
        int left = 0, right = nums.length - 1, mid = -1;
        
        if(nums == null || nums.length == 0){
            return new int[]{-1, -1};
        }
        
        while(right >= left){
            mid = (right + left) / 2;
            if(nums[mid] == target){
                break;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        
        int left2, right2, mid2 = -1;
        if(nums[mid] == target){
            right2 = right;
            left2 = mid;
            right = mid;
            
            while(right2 >= left2){
                mid2 = (right2 + left2) / 2;
                if(nums[mid2] > target){
                    right2 = mid2 - 1;
                }else{
                    left2 = mid2 + 1;
                }
            }
            
            while(right >= left){
                mid = (right + left) / 2;
                if(nums[mid] < target){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
        }else{
            return new int[]{-1, -1};
        }
        
        return new int[]{nums[mid] < target ? mid + 1 : mid, nums[mid2] > target ? mid2 - 1 : mid2};
    }
}

     当找到一个目标值后,再向两侧找目标值边界,二分法查找速度很快,再看另一种解法

class Solution {
    public int[] searchRange(int[] nums, int target) {

        return new int[] {lower_bound(nums, target),higher_bound(nums, target)};
    }

    private int higher_bound(int[] nums, int target){
            int left = 0;
            int right = nums.length-1;
            int res = -1;
            while (left <= right) {
                int mid = (right + left)/2;
                if (nums[mid] < target) {
                    left = mid +1;
                } else if (nums[mid]  == target) {
                    res = mid;
                    left = mid + 1;
                } else {

                    right = mid -1;
                }
            }
            return res;
        }

        private int lower_bound(int[] nums, int target){
            int left = 0;
            int right = nums.length-1;
            int res = -1;
            while (left <= right) {
                int mid = (right + left)/2;
                if (nums[mid] < target) {
                    left = mid +1;
                } else if (nums[mid]  == target) {
                    res = mid;
                    right = mid - 1;
                } else {
                    right = mid -1;
                }
            }
            return res;
        }
}

    与上面的想法差不多,找出target的上下界,不过上面求边界时利用了求得第一个target点时的left, right,更好一些

    算法-找到 K 个最接近的元素

给定一个排序好的数组,两个整数 k 和 x,从数组中找到最靠近 x(两数之差最小)的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样,优先选择数值较小的那个数。

示例 1:

输入: [1,2,3,4,5], k=4, x=3
输出: [1,2,3,4]

示例 2:

输入: [1,2,3,4,5], k=4, x=-1
输出: [1,2,3,4]

说明:

  1. k 的值为正数,且总是小于给定排序数组的长度。
  2. 数组不为空,且长度不超过 104
  3. 数组里的每个元素与 x 的绝对值不超过 104
class Solution {
    // 想法:先找到最接近x的数,往前包括这个数取k个数,这k个数是待选的,然后向后比较,若第一个
    // 数到x的距离大于最后一个数后面的一个数的距离,舍第一个数,加入下一个数,重复此操作
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = 1, right = arr.length - 2, mid = 0, index;
        
        if(x <= arr[0]){
            mid = 0;
        }else if(x >= arr[arr.length - 1]){
            mid = arr.length - 1;
        }else{
            while(left <= right){
                mid = (left + right) / 2;
                if(arr[mid] >= x && arr[mid - 1] < x){
                    break;
                }else if(arr[mid] < x){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
        }
        
        if(mid - k >= 0){
            index = mid - k;
        }else{
            index = 0;
        }
        
        while(index + k < arr.length && x - arr[index] > arr[index + k] - x){
            index++;
        }
        
        List<Integer> result = new ArrayList<>();
        for(int i = index; i < index + k; i++){
            result.add(arr[i]);
        }
        
        return result;
    }
}

     思路在注释里,用二分法,再看另一种解法

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int right=Arrays.binarySearch(arr,x);
        if(right<0){
            right=-right-1;
        }
        int n=arr.length;
        int left=right-1;//特殊情况,左侧无需考虑
        while(right<n&&arr[right]==x){
            right++;
        }
        while(left>=0&&arr[left]==x){
            left--;
        }
        //这里right和left都不等于x,1223
        int size=right-left-1;
        int[] resIdx=new int[2];
        while(size<k){
            if(right==n||(left>=0&&x-arr[left]<=arr[right]-x)){
                left--;
            }else{
                right++;
            }
            size++;
        }
        resIdx[0]=left+1;
        resIdx[1]=left+k;
        List<Integer> res=new ArrayList<>(k);
        for(int i=resIdx[0];i<=resIdx[1];i++){
            res.add(arr[i]);
        }
        return res;
    }
}

    先学一下Arrays.binarySearch的用法,会返回目标的索引或最接近目标的数组值的索引或负数(小于第一个数返回-1,大于最后一个数返回-1-array.length)

    这里先找到最接近(等于)target的点(用Arrays.binarySearch方法),然后向两侧找最接近的点

    算法-寻找峰值

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。

数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞。

示例 1:

输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素,你的函数应该返回其索引 2。

示例 2:

输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5 
解释: 你的函数可以返回索引 1,其峰值元素为 2;
     或者返回索引 5, 其峰值元素为 6。

说明:

你的解法应该是 O(logN) 时间复杂度的。

class Solution {
    public int findPeakElement(int[] nums) {
        if(nums == null || nums.length == 0){
            return -1;
        }else if(nums.length == 1){
            return 0;
        }
        
        int i = 0;
        while(++i < nums.length){
            if(nums[i-1] > nums[i]){
                return i-1;
            }
        }
        
        return nums.length - 1;
    }
}

    很简单的做法,从前向后找,当出现前一个比后一个大时,前一个就是峰,但是是O(n)复杂度的,看一种二分法的做法

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length -1;
        while(left<right) {
            int mid = (left+right)/2;
            if(mid >0 && nums[mid] < nums[mid-1]) {
                right = mid-1;
            } else if(nums[mid] < nums[mid+1]) {
                left = mid+1;
            } else {
                return mid;
            }
            
        }
        return left;
    }
}

    这里当mid比前一个(mid-1)小的时候,开始到mid-1一定有峰(因为mid比mid-1小,如果mid-2比mid-1小,那么mid-1是峰,即此时已有后一个(设为x+1)比前一个(设为x)小的情况,此时如果再出现x-1比x小,那么x是峰,如果没有这种情况,即只有x+1小于x,但x-1大于x,那么0处是峰,对于mid<mid+1的情况类似(这里的mid, x是数组索引,比较的是索引处的数组元素值)


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!