文章目录
题目描述思路 & 代码1. 暴力法2. 二分法3. 二分法——简略版题目描述
老套路了,有序找元素,直接冲二分思路是不难想,就是边界条件限制条件有点恶心,时不时爆个栈思路 & 代码
1. 暴力法
一次遍历找到left,right。时间复杂度O(n)
2. 二分法
当然其实findLeft & findRight可以合并成一个函数,用flag来表示找left还是right。此处便于理解,就不合并了不断缩小范围,找到了就先存着,然后继续缩小范围找。class Solution {public int[] searchRange(int[] nums, int target) {// 二分int[] ans = new int[]{-1,-1};if(nums == null || nums.length == 0){return ans;}// 初始化结束ans[0] = findLeft(nums,target);if(ans[0] != -1){ans[1] = findRight(nums,target);}return ans;}int findLeft(int[] nums,int target){int ans = -1;int left = 0, right = nums.length-1;while(left < right){int half = (right + left)/2;// 选左区间if(nums[half] > target){right = half - 1;}else if (nums[half] < target){left = half + 1;}else if (nums[half] == target){ans = half;right = half - 1;}}if(target == nums[left]){ans = left;}return ans;}int findRight(int[] nums,int target){int ans = -1;int left = 0, right = nums.length-1;while(left < right){int half = (right + left)/2;// 选左区间if(nums[half] > target){right = half - 1;}else if (nums[half] < target){left = half + 1;}else if (nums[half] == target){ans = half;left = half + 1;}}if(target == nums[right]){ans = right;}return ans;}}
3. 二分法——简略版
class Solution {public int[] searchRange(int[] nums, int target) {// 二分int[] ans = new int[]{-1,-1};if(nums == null || nums.length == 0){return ans;}// 初始化结束ans[0] = findLeftOrRight(nums, target, true);if(ans[0] != -1){ans[1] = findLeftOrRight(nums, target, false);}return ans;}int findLeftOrRight(int[] nums, int target, boolean isFindLeft){int ans = -1;int left = 0, right = nums.length-1;while(left < right){int half = (right + left) / 2;// 选左区间if(nums[half] > target){right = half - 1;}// 选右区间else if (nums[half] < target){left = half + 1;}// 根据找第一个 or 最后一个来进行赋值else if (nums[half] == target){ans = half;// 找第一个,往左区间走if(isFindLeft) {right = half - 1;}// 找最后一个,往右区间走else {left = half + 1;}}}if(target == nums[left]){ans = left;}return ans;}}