网站后台点击添加图片没有反应,策划文案的网站,集团 投入巨资 做网站,网站制作完成后作者#xff1a;reed#xff0c;一个热爱技术的斜杠青年#xff0c;程序员面试联合创始人前文回顾#xff1a;leetcode1. 两数之和--每天刷一道leetcode系列#xff01;leetcode2. 两数相加--每天刷一道leetcode系列#xff01;leetcode3. 无重复字符的最长子串--每天刷一… 作者reed一个热爱技术的斜杠青年程序员面试联合创始人前文回顾leetcode1. 两数之和--每天刷一道leetcode系列leetcode2. 两数相加--每天刷一道leetcode系列leetcode3. 无重复字符的最长子串--每天刷一道leetcode系列leetcode4. 寻找两个有序数组的中位数--每天刷一道leetcode系列leetcode5.最长回文子串--每天刷一道leetcode系列!leetcode9. 回文数--每天刷一道leetcode系列leetcode11. 盛最多水的容器--每天刷一道leetcode系列leetcode14. 最长公共前缀--每天刷一道leetcode算法题系列leetcode15. 三数之和--每天刷一道leetcode算法系列leetcode16. 最接近的三数之和--每天刷一道leetcode算法系列leetcode17. 电话号码的字母组合--每天刷一道leetcode算法系列leetcode18. 四数之和--每天刷一道leetcode算法系列leetcode19. 删除链表的倒数第N个节点--每天刷一道leetcode算法系列leetcode20. 括号生成--每天刷一道leetcode算法系列leetcode21. 合并两个有序链表--每天刷一道leetcode算法系列leetcode22. 括号生成--每天刷一道leetcode算法系列leetcode23. 合并K个排序链表--每天刷一道leetcode算法系列leetcode24. 两两交换链表中的节点--每天刷一道leetcode算法系列leetcode25. K个一组翻转链表--每天刷一道leetcode算法系列leetcode26. 删除排序数组中的重复项--每天刷一道leetcode算法系列!leetcode27. 移除元素--每天刷一道leetcode算法系列leetcode32. 最长有效括号--每天刷一道leetcode算法系列leetcode33. 搜索旋转排序数组--每天刷一道leetcode算法系列leetcode 34. 在排序数组中查找元素的第一个和最后一个位置--每天刷一道leetcode算法系列(本篇)题目描述给定一个按照升序排列的整数数组 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]分析本题是一个典型的二分查找类题目。题目的意思很明确就是寻找左边界和右边界。二分查找看似很简单其实里面的变化还是蛮多的。如何寻找左边界呢1.1如果nums[mid] target那么左边没有target。start mid1 1.2如果nums[mid]target在正常的二分查找中这种情况是可以直接返回结果。但是因为我们是要查找左边界这就有可能mid的左边还有可能有target这个数。因此需要进行两步操作。 1.2.1 用一个变量res标记mid的值如果左边还有数值等于target则更新res的值。否则直接返回res即可。 1.2.2 end mid - 1继续向左查找。1.3 如果nums[mid] target, 同1.2.2 end mid - 1继续向左查找。如何寻找右边界呢2.1如果nums[mid] target那么右边没有target。end mid - 12.2如果nums[mid]target在正常的二分查找中这种情况是可以直接返回结果。但是因为我们是要查找右边界这就有可能mid的右边还有可能有target这个数。因此需要进行两步操作。 2.2.1 用一个变量res标记mid的值如果左边还有数值等于target则更新res的值。否则直接返回res即可。 2.2.2 start mid 1继续向右查找。2.3 如果nums[mid] target, 同1.2.2 start mid 1继续向右查找。其实说白了找target找target的左边界或者找target的右边界仅仅是在nums[mid]target的处理上有差别。代码public int[] searchRange(int[] nums, int target) { assert nums! null; if(nums.length 0){ return new int[]{-1,-1}; } int[] res new int[]{findLeft(nums, target),findRight(nums, target)}; return res; } private int findLeft(int[] nums, int target){ int len nums.length; int res -1; int start 0; int end len - 1; while (start end){ int mid start (end - start)/2; if(nums[mid] start mid 1; } else { if(nums[mid] target){ res mid; } end mid - 1; } } return res; } private int findRight(int[] nums, int target){ int len nums.length; int res -1; int start 0; int end len - 1; while (start end){ int mid start (end - start)/2; if(nums[mid] target){ end mid - 1; } else { if(nums[mid] target){ res mid; } start mid 1; } } return res; }长按订阅更多面经分享
