栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

二叉查找树(重复元素情况)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

二叉查找树(重复元素情况)

二叉树查找元素的位置(含有重复元素,且元素个数是不确定的)

代码解析
package 在排序数组中查找第一个元素与最后一个元素;

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result =new int[2];
        result[0] = findFirstLeft2(nums,target);
        result[1] = findFirstRight2(nums,target);
        return result;
    }
    
//正常不包含重复元素时利用二分查找法查找元素
    public static int findFirstLeft(int[] nums, int target){
        int left = 0;
        int right = nums.length-1;
        while (left <= right){
            int mid = left+(right-left+1)/2;
            //比较目标值和中间值的大小;
            if(nums[mid] > target){
                //说明目标值在mid的左边,缩小范围
                right = mid-1;
            }else if(nums[mid] < target){
                left = mid+1;
            }else {
                return mid;
            }
        }
        return -1;
    }
//包含相同元素,则要判断该元素是首元素还是末元素。
    public static int findFirstLeft2(int[] nums , int target){
        int left = 0;
        int right = nums.length-1;
        while (left <= right){
            int mid = left+(right-left+1)/2;
            //比较目标值和中间值的大小;
            if(nums[mid] > target){
                //说明目标值在mid的左边,缩小范围
                right = mid-1;
            }else if(nums[mid] < target){
                left = mid+1;
            }else {
                //因为该数组是按照升序排序的,所以只要判断该元素
                //前一个元素是否相同,就知道该元素是第一个还是第二个
                if(mid == 0 || nums[mid] != nums[mid-1]){//mid == 0是防止mid-1超出数组范围。
                    //说明mid就是第一个元素
                    return mid;
                }else {
                    //说明该元素前面还有相同的元素,但是具体有几个,我们不秦楚
                    //所以我们不能直接返回前一个元素的位置,而是缩小范围,继续找第一个元素。
                    right = mid-1;
                }
            }
        }
        return -1;
    }

    //查找最后一个元素的位置
    public static int findFirstRight2(int[] nums , int target){
        int left = 0;
        int right = nums.length-1;
        while (left <= right){
            int mid = left+(right-left+1)/2;
            //比较目标值和中间值的大小;
            if(nums[mid] > target){
                //说明目标值在mid的左边,缩小范围
                right = mid-1;
            }else if(nums[mid] < target){
                left = mid+1;
            }else {
                //因为该数组是按照升序排序的,所以只要判断该元素
                //前一个元素是否相同,就知道该元素是第一个还是第二个
                if(mid == nums.length-1 || nums[mid] != nums[mid+1]){//如果mid为最后一个元素,就不存在下一个元素了
                    //说明mid就是第一个元素
                    return mid;
                }else {
                    //说明该元素前面还有相同的元素,但是具体有几个,我们不秦楚
                    //所以我们不能直接返回前一个元素的位置,而是缩小范围,继续找第一个元素。
                    left = mid+1;
                }
            }
        }
        return -1;
    }


}

代码解读

相比于传统的二叉树查找,多了一步判断元素是第一元素还是最后元素的操作。代码中都有解析。

复杂度分析

时间复杂度:O(logn)
空间复杂度:O(1)

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/946702.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号