文章目錄

• 題目描述
• 思路 & 代碼
• • • 1. 暴力法
    • 2. 二分法
    • 3. 二分法——簡略版

題目描述

• 老套路了，有序找元素，直接沖二分
• 思路是不難想，就是邊界條件限制條件有點(diǎn)惡心，時不時爆個棧
  

思路 & 代碼

1. 暴力法

一次遍歷找到left，right。時間復(fù)雜度O(n）

2. 二分法

• 當(dāng)然其實(shí)findLeft & findRight可以合并成一個函數(shù)，用flag來表示找left還是right。此處便于理解，就不合并了
• 不斷縮小范圍，找到了就先存著，然后繼續(xù)縮小范圍找。

class Solution {public int[] searchRange(int[] nums, int target) {// 二分int[] ans = new int[]{-1,-1};if(nums == null || nums.length == 0){return ans;}// 初始化結(jié)束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;// 選左區(qū)間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;// 選左區(qū)間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;}// 初始化結(jié)束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;// 選左區(qū)間if(nums[half] > target){right = half - 1;}// 選右區(qū)間else if (nums[half] < target){left = half + 1;}// 根據(jù)找第一個 or 最后一個來進(jìn)行賦值else if (nums[half] == target){ans = half;// 找第一個，往左區(qū)間走if(isFindLeft) {right = half - 1;}// 找最后一個，往右區(qū)間走else {left = half + 1;}}}if(target == nums[left]){ans = left;}return ans;} }

總結(jié)

以上是生活随笔為你收集整理的【LeetCode笔记】34. 在排序数组中查找元素的第一个和最后一个位置（Java、二分）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。