JAVA练习339- 搜索旋转排序数组-北京尧图网络

题目概览整数数组nums按升序排列数组中的值互不相同。在传递给函数之前nums在预先未知的某个下标k0 k nums.length上进行了向左旋转使数组变为[nums[k], nums[k1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]下标从 0 开始计数。例如[0,1,2,4,5,6,7]下标3上向左旋转后可能变为[4,5,6,7,0,1,2]。给你旋转后的数组nums和一个整数target如果nums中存在这个目标值target则返回它的下标否则返回-1。你必须设计一个时间复杂度为O(log n)的算法解决此问题。示例 1输入nums [4,5,6,7,0,1,2], target 0输出4示例 2输入nums [4,5,6,7,0,1,2], target 3输出-1示例 3输入nums [1], target 0输出-1提示1 nums.length 5000-10^4 nums[i] 10^4nums中的每个值都独一无二题目数据保证nums在预先未知的某个下标上进行了旋转-10^4 target 10^4来源33. 搜索旋转排序数组 - 力扣LeetCode解题分析方法二分法我们可以先尝试进行二分以 [5,6,0,1,2,3,4] 为例第一次二分之后的子数组为 [ 5,6,0,1 ] 和 [ 2,3,4]这样得到的子数组至少有一个时递增的令中间索引为 mid开始索引为 i结束索引为 j那么当 nums[ mid ] target 时返回 mid当 nums[ mid ] target 时看左子数组是否为递增数组nums[ i ] nums[mid] )若是则看 nums[ i ] 是否小于等于 target 若小于等于 target 则在左子数组中j mid - 1大于 target 则还在右边数组中i mid 1;若不是说明右子数组是递增数组target 还在左边数组中j mid - 1当 nums[ mid ] target 时看右子数组是否为递增数组nums[ j ] nums[mid] )若是则看 nums[ j ] 是否大于等于 target 若大于等于 target 则在右子数组中i mid 1小于 target 则还在右边数组中j mid - 1;若不是说明左子数组是递增数组target 还在右边数组中i mid 1时间复杂度O(logn)空间复杂度O(1)class Solution { public int search(int[] nums, int target) { int n nums.length; int i 0, j n-1; while(i j) { int mid (i j) / 2; if (nums[mid] target) { return mid; } if (nums[mid] target) { if (nums[i] nums[mid] nums[i] target) { i mid 1; } else { j mid - 1; } } else { if (nums[j] nums[mid] nums[j] target) { j mid - 1; } else { i mid 1; } } } return -1; } }

JAVA练习339- 搜索旋转排序数组

相关推荐

行业内知名的仿生木皮供应商哪家靠谱

射频采样ADC直采架构解析：从JESD204C同步到ADC12DJ5200RF实战

MSP430FR267x外设配置与低功耗设计实战指南

更多资讯

Linux下Oracle 11gR2单实例安装与避坑全流程

E-R图转关系模式实战与数据库设计全流程

MySQL线程池高并发压测：从TPS到stall_limit

RSIAgent：让智能体在新环境中递归自我进化的工程实践

空间智能平台：城市治理的数字孪生实践

Oracle EBS ASCP高级供应链计划实战：多工厂手机制造案例配置与验收

今日更新

AI辅助技术栈评估：提升研发决策效率60%

从生成Token到直接决策：Jev如何重塑AI Agent工程实践

32G统一内存跑大模型：内存账、TPS实测与端云分流

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？