当前位置: 首页 > article >正文

LeetCode33题:搜索旋转排序数组(原创)

【题目描述】

整数数组 nums 按升序排列,数组中的值 互不相同 。

在传递给函数之前,nums 在预先未知的某个下标 k0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], ..., 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
  • -104 <= nums[i] <= 104
  • nums 中的每个值都 独一无二
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  • -104 <= target <= 104

题目链接:33. 搜索旋转排序数组 - 力扣(LeetCode)

【解题代码】

package array;

public class Search {

    public static void main(String[] args) {
        //int nums[] = new int[]{4, 5, 6, 7, 0, 1, 2}, target = 0;
        //int nums[] = new int[]{4, 5, 6, 7, 8, 1, 2, 3}, target = 8;
        //int nums[] = new int[]{8, 1, 2, 3, 4, 5, 6, 7}, target = 6;
        //int nums[] = new int[]{4, 5, 6, 7, 8, 1, 2, 3}, target = 8;
        //int nums[] = new int[]{3, 5, 1}, target = 3;
        int nums[] = new int[]{5, 1, 2, 3, 4}, target = 1;

        //int result = new Search().binarySearch(nums, 0, nums.length - 1, target);
        int result = new Search().search(nums, target);
        System.out.println("计算结果:" + result);
    }

    public int search(int[] nums, int target) {
        int start = 0, end = nums.length - 1;
        while (start <= end) {
            if (nums[start] == target) return start;
            if (nums[end] == target) return end;

            int middle = start + (end - start) / 2;
            if (nums[middle] == target) return middle;

            if (nums[middle] < nums[end]) {
                if (target > nums[middle] && target < nums[end])
                    start = middle + 1;
                else
                    end = middle - 1;
            } else {
                if (target > nums[start] && target < nums[middle])
                    end = middle - 1;
                else
                    start = middle + 1;
            }
        }

        return -1;
    }
}

【解题思路】

这道理分析一下,感觉是对二分检索法的一个变体,根据各种情况,反复思索得出以下思路:

  1. 首先根据首索引start,和尾索引end计算出中间索引middile;
  2. 如果目标值等于中间值直接返回结果,否则继续分段查找
  3. 首先中间值如果小于尾值,那么说明中间值与尾值必然在同一个递增序列里,如果目标值在递增序列的条件就是,目标值大于中间值且小于尾值;
  4. 否则首值和中间值必然在同一个递增序列里,如果目标值在递增序列的条件就是,目标值大于首值且小于中间值;
  5. 然后根据2,3的判断条件,不断循环改变当前的首尾索引值,并进行判断
  6. 最后如果没有结果返回-1

根据以上思路,编写并多次调试代码,最终完成代码提交并运行成功

【解题步骤】

  1. 定义首尾索引值,然后不断循环比较首尾索引值大小,直到首索引值大于尾索引值
    int start = 0, end = nums.length - 1;
    while (start <= end) {
        ...
    }
  2. 如果目标数值等于首尾数值,直接返回结果
    if (nums[start] == target) return start;
    if (nums[end] == target) return end;
  3. 计算中间索引值,如果中间数值等于目标数值,直接返回结果
    int middle = start + (end - start) / 2;
    if (nums[middle] == target) return middle;
  4. 如果中间数值小于尾数值,那么说明中间数值和尾数值是在同一递增序列,那么如果目标值在此递增序列的条件就是大于中间数值并且小于尾数值,否则则是在另一数列
     if (nums[middle] < nums[end]) {
        if (target < nums[end] && target > nums[middle])
            start = middle + 1;
        else
            end = middle - 1;
    }
  5. 如果中间数值大于尾数值,那么说明首数值和中间数值是在同一递增序列,那么如果目标值在此递增序列的条件就是大于首数值并且小于中间数值,否则则是在另一数列
    else {
        if (target > nums[start] && target < nums[middle])
            end = middle - 1;
        else
            start = middle + 1;
    }

【思考总结】

  1. 此题的关键点在于当前二分数组最多有两个递增序列,需要判断中间值在和首值还是尾值在同一个递增序列。然后根据目标值判断是否在此递增序列,然后根据目标值所在位置,不断地更新二分检索范围
  2. 此算法是二分检索法的一个变体,需要灵活变通的去思考,挺有意义的
  3. LeetCode解题之前,一定不要看题解,看了就“破功”了!

http://www.kler.cn/a/450922.html

相关文章:

  • 2024年全球薄膜功率电感器行业总体规模、主要企业国内外市场占有率及排名
  • xdoj 数字个数统计
  • 重塑数字文档处理:TX Text Control的2024年里程碑
  • java如何使用poi-tl在word模板里渲染多张图片
  • 【教程】第十一章 子任务 工时——化繁为简
  • Docker快速入门到项目部署
  • 【VMware虚拟机】安装win10系统教程双机可ping通
  • leetcode hot100回文字符串的链表
  • 帝国CMS:如何去掉帝国CMS登录界面的认证码登录
  • 类OCSP靶场-Kioptrix系列-Kioptrix Level 5(2014)
  • GB/T34944-2017 《Java语言源代码漏洞测试规范》解读——行为问题、路径错误、处理程序错误
  • 光谱相机在农业中的具体应用案例
  • C/C++ 数据结构与算法【数组】 数组详细解析【日常学习,考研必备】带图+详细代码
  • zabbix监控山石系列Hillstone监控模版(适用于zabbix7及以上)
  • vue实现打印指定页面内容
  • 消除视野盲区,保障行车安全--叉车四路环绕AI防撞系统
  • 迈向未来:.NET技术的持续创新与发展前景
  • 【华为OD-E卷-木板 100分(python、java、c++、js、c)】
  • Naive UI 分页组件二次封装
  • Dubbo简单总结
  • 【蓝桥杯——物联网设计与开发】基础模块8 - RTC
  • GitPuk安装配置指南
  • LEC: 基于Transformer中间层隐藏状态的高效特征提取与内容安全分类方法
  • 武汉做网站优化推广效果的科学评估方法
  • redis库基础知识
  • SpringBoot开发——Spring Boot 的9大类常用注解